LOJ 10224 GT 考试

题目链接

设\(f[i][j]\)表示考虑准考证号\(i\)的后缀与 A 长度为\(j\)的前缀匹配的方案数。
\(f[i][j]=\sum\limits_{k=0}^{n}f[i-1][k]\times g[k][j]\)
\(g[k][j]\)表示填入有多少个数字使匹配长度从\(k\)变成\(j\)
第二个可以用 kmp 预处理。
dp 方程是矩乘的形式，可以用矩阵乘法优化。

#include <bits/stdc++.h>
using namespace std;

const int N = 30;
int n, m, MOD, f[N], mc[N][N];
char s[N];

struct Martix {
	int x, y, f[N][N];
	Martix (int X, int Y) {
        x = X, y = Y;
		memset(f, 0, sizeof f);
	}
	Martix operator * (const Martix& q) const {
		Martix t(x, q.y);
		for (int i = 0; i < t.x; i++)
			for (int j = 0; j < t.y; j++)
				for (int k = 0; k < y; k++) t.f[i][j] = (1ll * t.f[i][j] + f[i][k] * 1ll * q.f[k][j]) % MOD;
		return t;
	}
};

void kmp() {
    f[0] = -1;
    for (int i = 1; i <= m; ++i) {
        int j = f[i - 1];
        while (s[j + 1] != s[i] && j != -1) j = f[j];
        f[i] = j + 1;
    }
    f[0] = 0;
    for (int i = 0; i < m; i++) {
        for (int j = '0'; j <= '9'; j++) {
            int tmp = i;
            while (s[tmp + 1] != j && tmp > 0) tmp = f[tmp];
            if (s[tmp + 1] == j)
                tmp++;
            mc[i][tmp]++;
        }
    }
}

Martix fpow(Martix c, int b) {
	Martix res(m, m);
	for (int i = 0; i <= m; i++) res.f[i][i] = 1;
	for (; b; b >>= 1, c = c * c) if (b & 1) res = c * res;
	return res;
}

int main() {
    scanf("%d %d %d", &n, &m, &MOD);
    scanf("%s", s + 1);
    kmp();
    Martix g(m, m), a(m, 1);
    a.f[0][0] = 1;
    for (int i = 0; i <= m; i++)
    	for (int j = 0; j <= m; j++) g.f[i][j] = mc[i][j];
    g = fpow(g, n);
    a = a * g;
    int ans = 0;
    for (int i = 0; i < m; i++) ans = (ans + a.f[0][i]) % MOD;
    printf("%d\n", ans);
    return 0;
}