1009: [HNOI2008]GT考试

https://www.lydsy.com/JudgeOnline/problem.php?id=1009

分析：

　　f[i][j]表示第一个字符串到i,与第二个匹配了j个的方案数。新加一个字符，如果第一个字符串仍与第二个一样，那么转移到f[i+1][j+1]，否则，转移到f[i+1[k]，k是不确定的。预处理g[i][j]表示两个字符串匹配了i，然后增加一个字符后，匹配的位数变成j后的方案数。

　　那么有转移方程：$dp[i][j]=sum_{0<=k<=m-1}dp[i-1][k] imes g[k][j]$

　　然后发现n特别大，但是每个i转移只有20-1（等于m了，就不用记录了）个，所以可以矩阵快速幂。

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<cctype>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 #include<map>
11 using namespace std;
12 typedef long long LL;
13 
14 inline int read() {
15     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
16     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
17 }
18 
19 const int N = 100;
20 
21 int p[N], g[N][N];
22 char s[N];
23 int n, m, mod;
24 
25 struct Matrix{
26     int a[N][N];
27     void init() {
28         for (int i=0; i<m; ++i) a[i][i] = 1;
29     }
30     void Clear() {
31         memset(a, 0, sizeof(a));
32     }
33 }A;
34 Matrix mul(Matrix A, Matrix B) {
35     Matrix C; C.Clear();
36     for (int k=0; k<m; ++k) 
37         for (int i=0; i<m; ++i)
38             for (int j=0; j<m; ++j) 
39                 C.a[i][j] = (C.a[i][j] + 1ll * A.a[i][k] * B.a[k][j] % mod) % mod;
40     return C;
41 }
42 Matrix ksm(Matrix a,int b) {
43     Matrix res; res.Clear(); res.init();
44     while (b) {
45         if (b & 1) res = mul(res, a);
46         a = mul(a, a);
47         b >>= 1;
48     }
49     return res;
50 }
51 void KMP() {
52     p[1] = 0;
53     for (int i=2; i<=m; ++i) {
54         int j = p[i - 1];
55         while (j && s[j + 1] != s[i]) j = p[j];
56         if (s[j + 1] == s[i]) j ++;
57         p[i] = j;
58     }
59     for (int i=0; i<=m; ++i) {
60         for (int j='0'; j<='9'; ++j) {
61             int k = i;
62             while (k && s[k + 1] != j) k = p[k];
63             if (s[k + 1] == j) g[i][k + 1] ++;
64             else g[i][0] ++;
65         }
66     }
67 }
68 int main() {
69     n = read(), m = read(), mod = read();
70     scanf("%s",s+1);
71     KMP();
72     for (int i=0; i<=m; ++i) 
73         for (int j=0; j<=m; ++j) 
74             A.a[i][j] = g[i][j];
75     A = ksm(A, n);
76     int Ans = 0;
77     for (int i=0; i<m; ++i) 
78         Ans = (Ans + A.a[0][i]) % mod;
79     cout << Ans;
80     return 0;
81 }