首页 > 代码库 > 【不可能的任务17/200】bzoj1009矩阵快速面+kmp
【不可能的任务17/200】bzoj1009矩阵快速面+kmp
其实kmp真的很次要，求长度为20的kmp感觉真的有点杀鸡用牛刀
这题思路相当明确：一看题就是数位dp，一看n的大小就是矩阵
矩阵的构造用m*m比较方便，本来想写1*m的矩阵乘m*m的，但是感觉想起来太麻烦就偷懒，没想到1A了
log的速度的确可以，87ms贼快，好久没见这么短的运行时间了
1 #include <cstdio> 2 int n,m,mod,k; 3 char ch; 4 int a[100],ne[100]; 5 int ans[100][100],t[100][100],zy[100][100]; 6 void mul(bool b) 7 { 8 for(int i=0;i<m;i++) 9 for(int j=0;j<m;j++)10 for(k=0,t[i][j]=0;k<m;k++)11 t[i][j]=(t[i][j]+(b?ans[i][k]:zy[i][k])*zy[k][j])%mod;12 for(int i=0;i<m;i++)13 for(int j=0;j<m;j++)14 if(b) ans[i][j]=t[i][j];15 else zy[i][j]=t[i][j];16 if(b) n--;else n/=2;17 }18 int main()19 {20 scanf("%d%d%d",&n,&m,&mod);21 for(ch=getchar();ch<‘0‘ || ch>‘9‘;ch=getchar());22 for(int i=1;i<=m;i++,ch=getchar())23 a[i]=ch-‘0‘;24 for(int i=2;i<=m;i++)25 {26 int k=ne[i-1];27 while(k && (a[k+1]!=a[i])) k=ne[k];28 ne[i]=k+(a[k+1]==a[i]);29 }30 for(int i=0;i<m;i++)31 for(int j=0;j<=9;j++)32 {33 int k=i;34 while(k && a[k+1]!=j) k=ne[k];35 k+=(a[k+1]==j);36 if(k!=m) zy[k][i]++;37 }38 for(int i=0;i<m;i++)39 ans[i][i]=1;40 while(n)41 mul(n&1);42 int sum=0;43 for(int i=0;i<m;i++)44 sum=(sum+ans[i][0])%mod;45 printf("%d",sum);46 return 0;47 }
【不可能的任务17/200】bzoj1009矩阵快速面+kmp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。