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

題意：

?

思路：
真的是好題啊！

對于這種題目，很有可能就是dp，$f[i][j]$表示分析到第 i 位時匹配了不吉利數(shù)字的前 j 位，那么對于第i+1位來說，它有3種情況：

①加入第i +1位后，和不吉利數(shù)字不匹配了，也就是變成了$f[i+1][0]$。

②這種情況還是不匹配，但是它不回到0，這個就是kmp，這樣一說是不是想明白了。

③繼續(xù)匹配，也就是$f[i+1][j+1]$。

這個計算的話可以用矩陣來加速：

$a[i][j]$表示從匹配i個數(shù)變到匹配j個數(shù)的方法數(shù)。$a[i][j]$的初始化就靠kmp來完成了。

1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,ll> pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn=100+5; 17 18 int n, m, mod; 19 char s[25]; 20 int nxt[maxn]; 21 22 struct Matrix 23 { 24 int mat[30][30]; 25 Matrix operator *(Matrix a) 26 { 27 Matrix c; 28 for(int i=0;i<m;i++) 29 { 30 for(int j=0;j<m;j++) 31 { 32 c.mat[i][j]=0; 33 for(int k=0;k<m;k++) 34 c.mat[i][j]=(c.mat[i][j]+mat[i][k]*a.mat[k][j])%mod; 35 } 36 } 37 return c; 38 } 39 }base,a; 40 41 void qpow(int n) 42 { 43 for(int i=0;i<m;i++) 44 { 45 a.mat[i][i]=1; 46 for(int j=i+1;j<m;j++) 47 a.mat[i][j]=a.mat[j][i]=0; 48 } 49 50 while(n) 51 { 52 if(n&1) a=a*base; 53 base=base*base; 54 n>>=1; 55 } 56 } 57 58 void get_next() 59 { 60 int i = -1, j = 0; 61 nxt[0] = -1; 62 while (j < m) 63 { 64 if (i == -1 || s[i] == s[j]) 65 nxt[++j] = ++i; 66 else 67 i = nxt[i]; 68 } 69 } 70 71 void kmp() 72 { 73 memset(base.mat,0,sizeof(base.mat)); 74 75 for(int i=0;i<m;i++) 76 { 77 for(char j='0';j<='9';j++) 78 { 79 int k=i; 80 while(k && s[k]!=j) k=nxt[k]; 81 if(s[k]==j) k++; 82 if(k!=m) base.mat[i][k]++; 83 } 84 } 85 } 86 87 int main() 88 { 89 //freopen("in.txt","r",stdin); 90 while(~scanf("%d%d%d%s",&n,&m,&mod,s)) 91 { 92 get_next(); 93 kmp(); 94 qpow(n); 95 int ans=0; 96 for(int i=0;i<m;i++) 97 ans=(ans+a.mat[0][i])%mod; 98 printf("%d\n",ans); 99 } 100 return 0; 101 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zyb993963526/p/7324998.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1009: [HNOI2008]GT考试（kmp+dp+矩阵优化）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。