Kattis Message （状态机模型 + 矩阵快速幂）

spirit

2021 年 06 月 15 日

4094 次浏览

暂无评论

1625字数

VJ训练赛状态机模型

# Kattis Message （状态机模型 + 矩阵快速幂）

[题目链接](https://vjudge.net/problem/Kattis-message)

## 题意

给出一个长度不超过 $50$ 的字符串 $p$ ，求出所有长度为 $n$ 且包含 $p$ 作为子串的字符串个数 $K$ ，答案对 $M$ 取余。（所有字符串均只包含小写英文字母）

**Input**

第一行输入 $T$ 表示共有 $T$ 组输入。

每组数据的第一行是 $n$ 和 $M$ ，第二行为字符串 $p$ 。

```
2
2 100
ab
3 100
ab
```

**Output**

输出 $K \% M$ 。

```
1
52
```

## 思路

定义 $dp_{i,j}$ 为长度为 $i$ ，与 $p$ 串前缀相同的最长后缀长度为 $j$ 的字符串个数。例如 $p$ 串为 $abcde$ ，满足 $dp_{5,3}$ 的字符串的形式为 $\ast \ast abc$ 。特别定义一点，若 $p$ 串长度为 $m$ ，则 $dp_{i,m}$ 是包含 $p$ 串作为子串且长度为 $i$ 的字符串的数量。

$KMP$ **求转移方程矩阵**

转移矩阵 $b$ 的定义：$b_{j,k}$ 代表 $dp_{i,j}$ 可以转移到 $dp_{i+1,k}$ 上，即在由 $dp_i$ 向 $dp_{i+1}$ 转移的过程中需要进行操作 $dp_{i+1,k} += b_{j,k} \times dp_{i,j}$ 。

可以注意到字符串中只有小写英文字母，所以我们考虑枚举在满足 $dp_{i,j}$ 的字符串后面添加 $a - z$ 就可以了。比如说在上面的例子中，可知 $dp_{5,3}$ 的后缀一定是 $abc$ ，如果在后面加上一个字母 $d$ ，就可以变成长度为 $i + 1$ 、与 $p$ 串前缀相同的最长后缀长度为 $4$ 的字符串（即 $dp_{6,4}$ ）了，因此我们将 $b_{3,4}$ 加一。同时如果我们把 $dp_i$ 看做一个 $1$ 行 $m + 1$ 列的矩阵，可以发现在 $dp_i$ 的右边乘上一个转移矩阵 $b$ ，得到的结果就是 $dp_{i + 1}$ ，那么转移过程就可以用矩阵快速幂优化了。

由于 $dp_{i, m}$ 是特殊定义的，我们令 $b_{m, m} = 26$ ，即在已经包含 $p$ 串的字符串后无论添加哪个字母，得到的新字符串都包含 $p$ 作为子串。

## 代码

```cpp
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 55;
__int128 b[N][N];
LL n, mod;
char s[N];
int Next[N], m;
//矩阵乘法
void mul(__int128 a[][N], __int128 b[][N], __int128 c[][N]) {
    __int128 tmp[N][N] = {0};
    for (int i = 0; i <= m; i++)
    for (int j = 0; j <= m; j++)
    for (int k = 0; k <= m; k++)
        tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % mod;
    memcpy(c, tmp, sizeof tmp);
}
//矩阵快速幂
void fastPow(__int128 a[][N], LL k, __int128 c[][N]) {
    __int128 tmp[N][N] = {0};
    for (int i = 0; i <= m; i++) tmp[i][i] = 1;
    while (k) {
        if (k & 1) mul(tmp, a, tmp);
        k >>= 1;
        mul(a, a, a);
    }
    memcpy(c, tmp, sizeof tmp);
}
//求状态转移矩阵
void get_next() {
    memset(b, 0, sizeof b);
    int i = 0, j = -1;
    Next[0] = -1;
    b[m][m] = 26;
    while (i < m) {
        if (j == -1 || s[i] == s[j]) {
            Next[++i] = ++j;
        } else {
            j = Next[j];
        }
    }
    //枚举上一个转态，即这里的i是在枚举dp[i][j]的第二维
    for (int i = 0; i < m; i++)
    for (int c = 'a'; c <= 'z'; c++) {
        int k = i;
        while (k >= 0 && s[k] != c) k = Next[k];
        k++;
        b[i][k]++;
    }
}
int main() {
    int t;
    cin >> t;
    while (t --) {
        scanf("%lld %lld %s", &n, &mod, s);
        m = strlen(s);
        get_next();
        fastPow(b, n, b);
        LL res = b[0][m];
        printf("%lld\n", res);
    }
    return 0;
}
```

最后修改：2021 年 06 月 15 日