[BZOJ 1009][HNOI2008]GT考试
转载请注明出处：http://danihao123.is-programmer.com/
好劲啊这题……
首先先想DP的做法，我们用表示若字符串已匹配前缀
，有多少种方案使得追加上一个数后匹配
，这个用KMP可以很方便的求出
（事实上暴力也可以）。
然后再来看DP的做法，转移方程大致是这样的：
但是n非常大，这么做注定要TLE。
不过看这个转移方程，是不是和矩阵乘法的定义很像？是的。
我们可以用一个的矩阵
来表示某一个阶段的DP值，我们可以把
组织成一个
矩阵
。然后我们可以发现：
由于矩阵乘法满足结合律，所以：
很明显可以快速幂搞出来。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | /************************************************************** Problem: 1009 User: danihao123 Language: C++ Result: Accepted Time:80 ms Memory:820 kb****************************************************************/ #include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef unsigned long long ull;typedef ull Matrix[22][22];ull MOD;#define REP(i,n) for(i=0;i<(n);i++)#define CL_ARR(x,v) memset(x,v,sizeof(x))#define CP_ARR(from,to) memcpy(to,from,sizeof(from)) inline void MatrixMul(Matrix A,Matrix B,int m,int n,int p,Matrix& res){ register int i,j,k; Matrix C; CL_ARR(C,0); REP(i,m){ REP(j,p){ REP(k,n){ C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD; } } } CP_ARR(C,res);}void MatrixPow(Matrix A,int m,ull p,Matrix& res){ Matrix a,temp; register int i; CL_ARR(a,0); memcpy(a,A,sizeof(a)); CL_ARR(temp,0); REP(i,m){ temp[i][i]=1; } while(p){ if(1&p){ MatrixMul(temp,a,m,m,m,temp); } p>>=1; MatrixMul(a,a,m,m,m,a); } CP_ARR(temp,res);} char buf[25];int f[25];int main(){ register int i,u,j; register ull ret=0; ull n; int m; Matrix ans,P; scanf("%llu%d%llu",&n,&m,&MOD); scanf("%s",buf+1); CL_ARR(ans,0); ans[0][0]=1; CL_ARR(P,0); P[0][0]=9;P[0][1]=1; // f[0]=f[1]=0; for(i=1;i<m;i++){ u=f[i]; while(u && buf[u+1]!=buf[i+1]){ u=f[u]; } if(buf[u+1]==buf[i+1]){ f[i+1]=u+1; }else{ f[i+1]=0; } for(j=0;j<10;j++){ u=i; while(u && buf[u+1]!=j+'0'){ u=f[u]; } if(buf[u+1]==j+'0'){ P[i][u+1]=(P[i][u+1]+1)%MOD; }else{ P[i][0]=(P[i][0]+1)%MOD; } } } MatrixPow(P,m,n,P); MatrixMul(ans,P,1,m,m,ans); for(i=0;i<m;i++){ ret=(ret+ans[0][i])%MOD; } printf("%llu\n",ret); return 0;} |
评论 (0)
