嗯这题不是权限题 很友好
SA裸题
READ MORE →
XSYOJ 1133 兔子的字符串
题面大意是：
给一个长度为N的串
READ MORE →
BZOJ4278
BZOJ1009
随便搞搞转移矩阵……就是每个位上往后面拓展一位能拓展到哪些后缀
然后发现这个转移矩阵可以用快速幂来加速
于是随便搞搞了XD
|
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 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <cmath> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define BASE '0' int n,m,k; int a[25],b[25]; int mp[25][25],mp2[25][25],nxt[25][15],fail[25]; char st[25]; void solve() { a[0]=1; for(;n;n>>=1) { if(n&1) { For(i,0,m) { b[i]=0; for(int j=0;j<=m;j++) b[i]=(b[i]+a[j]*mp[j][i])%k; } For(i,0,m) a[i]=b[i]; } for(int _=0;_<=m;_++) for(int __=0;__<=m;__++) { mp2[_][__]=0; For(i,0,m) mp2[_][__]=(mp2[_][__]+mp[_][i]*mp[i][__])%k; } for(int _=0;_<=m;_++) for(int __=0;__<=m;__++) mp[_][__]=mp2[_][__]; // For(i,0,m) // for(int j=0;j<=m;j++) printf(j==m?"%d\n":"%d ",mp[i][j]); } } void bruteforce() { bool use[25][15]; memset(use,0,sizeof(use)); fail[0]=-1; fail[1]=0; int node=1; while(node) { if(!use[1][st[node+1]]) { nxt[1][st[node+1]]=node+1; use[1][st[node+1]]=1; } node=fail[node]; } for(int j=0;j<=9;j++) { int t=1; while(st[t+1]!=j&&t) t=fail[t]; if(st[t+1]==j) t++; nxt[1][j]=t; } for(int i=2,p=0;i<=m;i++) { node=i; while(st[i]!=st[p+1]&&p) p=fail[p]; if(st[p+1]==st[i]) p++; fail[i]=p; for(int j=0;j<=9;j++) { int t=i; while(st[t+1]!=j&&t) t=fail[t]; if(st[t+1]==j) t++; nxt[i][j]=t; } } } void init() { read(n); read(m); read(k); scanf("%s",st+1); for(int i=1;i<=m;i++) st[i]-=BASE; bruteforce(); // For(i,0,m) printf("%d\n",fail[i]); // For(i,0,m) // { // for(int j=0;j<10;j++) printf("%d ",nxt[i][j]); // puts(""); // } For(i,1,m-1) for(int j=0;j<=9;j++) mp[i][nxt[i][j]]++; mp[0][1]=1; mp[0][0]=9; mp[m][m]=10; // For(i,0,m) // for(int j=0;j<=m;j++) printf(j==m?"%d\n":"%d ",mp[i][j]); } int main() { init(); int ans=0; solve(); For(i,0,m-1) ans+=a[i]; ans%=k; printf("%d\n",ans); return 0; } |