首页 > > 程序设计 > C/C++ >

bzoj1009 [ HNOI2008 ] -- KMP+矩阵乘法加速DP

2018-06-17 23:06:12来源：未知阅读 ()

令f[i][j]表示前i个字符，匹配到不吉利数字的第j位的方案数。

枚举第i+1位，通过KMP求出前i+1个字符可以匹配到不吉利数字的第几位，递推。

但由于n<=10⁹，要用矩阵乘法加速。

f[i][j]=a[j][0]*f[i-1][0]+a[j][1]*f[i-1][1]+...+a[j][m-1]*f[i-1][m-1]

那么f[n]就是 aⁿ×f[0]

用快速幂，时间复杂度为O(log₂n*m³)

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define N 30
 6 struct J{
 7     int a[N][N];
 8 }a,b;
 9 int Ans,f[N],i,j,k,n,m,x,y;
10 char s[N];
11 inline J Ch(J a,J b){
12     J c;
13     for(int i=0;i<m;i++)
14     for(int j=0;j<m;j++){
15         c.a[i][j]=0;
16         for(int p=0;p<m;p++)
17         c.a[i][j]=(c.a[i][j]+a.a[i][p]*b.a[p][j])%k;
18     }
19     return c;
20 }
21 inline J Pow(J a,int y){
22     if(y==1)return a;
23     J c=Pow(a,y>>1);
24     c=Ch(c,c);
25     if(y&1)c=Ch(a,c);
26     return c;
27 }
28 int main()
29 {
30     scanf("%d%d%d%s",&n,&m,&k,s+1);
31     for(i=1;i<=m;i++)s[i]-=48;
32     for(f[1]=f[i=2]=1;i<m;i++){
33         j=f[i];
34         while(j>1&&s[j]!=s[i])j=f[j];
35         f[i+1]=s[j]==s[i]?j+1:1;
36     }
37     a.a[0][0]=1;
38     for(i=0;i<m;i++)
39     for(j=0;j<=9;j++){
40         for(x=i+1;x>1&&j!=s[x];x=f[x]);
41         if(j!=s[x])x=0;
42         if(x<m)b.a[i][x]=(b.a[i][x]+1)%k;
43     }
44     a=Ch(a,Pow(b,n));
45     for(i=0;i<m;i++)Ans=(Ans+a.a[0][i])%k;
46     printf("%d",Ans);
47     return 0;
48 }