Description

　　阿申準備報名參加GT考試，準考證號為N位數X1X2....Xn(0<=Xi<=9),他不希望準考證號上出現不吉利的數字。
他的不吉利數學A1A2...Am(0<=Ai<=9)有M位，不出現是指X1X2...Xn中沒有恰好一段等于A1A2...Am. A1和X1可以為
0

Input

　　第一行輸入N,M,K.接下來一行輸入M位的數。 N<=10^9,M<=20,K<=1000

Output

　　阿申想知道不出現不吉利數字的號碼有多少種，輸出模K取余的結果.

Sample Input

4 3 100?
111

Sample Output

81 /*我們用DP來解決這個問題W[i,j]表示準考證的第I位，和不吉利的數匹配到了第J位的方案數，這個狀態的表示也可以看成當前到第i位了，準考證的后J位是不吉利的數的前J位，的方案數那么我們最后的ans=ΣW[n,i] 0<=i<=m-1那么我們考慮怎么轉移假設當前到第I位了，匹配到第J位，也就是W[i,j]的值我們有了，我們可以枚舉第I+1位是什么，然后通過KMP的NEXT數組可以快速的得到當前枚舉的位可以匹配到第幾位，假設可以匹配到第P位，那么我們W[I+1,P]+=W[I,J]，這樣就可以轉移了但是我們看N的數據范圍是10^9，所以遞推是完不成的，這時候需要觀察下規律我們發現轉移時的P,J和I是沒有關系的，也就是不管I是幾，W[i,j]固定會加到W[i+1,k]上所以我們換一種轉移的方式，之前是用W[I,J]更新W[i,P]，現在我們可以寫成W[i,j]=a0*W[i-1,0]+a1*W[i-1,1]+......+a(m-1)*W[i-1,m-1]而且ai數組是不變的，那么這個式子就是“常系數線性齊次遞推式”,可以用矩陣乘法優化（不大懂為什么）。 */ #include<cstdio> #include<iostream> #define N 25 using namespace std; int n,m,p,fail[N],a[N][N],ans[N][N],c[N][N]; char s[N]; void kmp(){fail[1]=0;for(int i=2;i<=m;i++){int p=fail[i-1];while(p&&s[p+1]!=s[i])p=fail[p];if(s[p+1]==s[i])fail[i]=p+1;else fail[i]=0;}for(int i=0;i<m;i++)for(int j='0';j<='9';j++){int p=i;while(p&&s[p+1]!=j)p=fail[p];if(s[p+1]==j)a[i][p+1]++;else a[i][0]++;} } int main(){scanf("%d%d%d%s",&n,&m,&p,s+1);kmp();for(int i=0;i<m;i++)ans[i][i]=1;while(n){if(n&1){for(int i=0;i<m;i++)for(int j=0;j<m;j++)for(int k=0;k<m;k++)c[i][j]=(c[i][j]+a[i][k]*ans[k][j])%p;for(int i=0;i<m;i++)for(int j=0;j<m;j++)ans[i][j]=c[i][j],c[i][j]=0;}for(int i=0;i<m;i++)for(int j=0;j<m;j++)for(int k=0;k<m;k++)c[i][j]=(c[i][j]+a[i][k]*a[k][j])%p;for(int i=0;i<m;i++)for(int j=0;j<m;j++)a[i][j]=c[i][j],c[i][j]=0;n>>=1;}int sum=0;for(int i=0;i<m;i++)sum=(sum+ans[0][i])%p;printf("%d",sum);return 0; }

?

轉載于:https://www.cnblogs.com/shenben/p/6246539.html

總結

以上是生活随笔為你收集整理的GT考试（bzoj 1009）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。