【題目鏈接】:http://www.lydsy.com/JudgeOnline/PRoblem.php?id=1009
【題意】
【題解】 網上有幾個博客寫得挺好的. 這里發一下鏈接; 這一篇有把大概怎么做寫下來; http://www.cnblogs.com/BLADEVIL/p/3483694.html 而下面這一篇提到的細節比較好;也講得比較清楚些; http://blog.csdn.net/cjk_cjk/article/details/43038377 大概的思路: 假設你現在掃描到了你的準考證號的第i位,同時不吉利數字匹配到了第j位; 也就是說準考證上:i-j+1..i和不吉利數字的1..j匹配好了; 接下來要確定第i+1位是什么; 這里把第i+1位換成第i位,原來的第i位就變成i-1位; 設f[i][j]表示：準考證號前i位中 后j位與不吉利數的前j位相同時，前i位的方案數 則有 f[i][j]=f[i-1][0]*a[0][j]+f[i-1][1]*a[1][j]+…+f[i-1][m-1]*a[m-1][j] 這里的a[k][j]表示的是前一位如果匹配到了第k位,然后想通過增加一個數字變成i個數字 ,然后匹配到第j位,問在第i位有多少個數字可以選擇; 這個a數組可以預處理出來; 我們先考慮這個a數組的求法: 比如不吉利數字為 1231243 這里; 假設我們掃描到了第5個數字2; 那么我們就相當于讓第i-1個數字匹配到了第5個數字; 然后問你第i個狀態哪些狀態能由這第5個數字接受到? 它的下一個狀態應該可以接匹配到了第3和第6個數字; 即類似 *****12x ****12312x 可能用上面博客的例子好一點: 比如：還是假設不吉利數為123124，那么 f[i][3]=f[i-1][2]+f[i-1][5]，因為 f[i-1][2]末尾的*****12不能是**12312，所以需要f[i-1][5]補充 ; 這里的”不能是**12312“可以用一個判重的東西搞出來; 那么像上面這樣的a數組要怎么搞呢? KMP算法！ 具體的只能看程序了； (你需要理解KMP算法的思路才能搞,不然會看得暈頭轉向); 然后N這么大; 你肯定得寫個矩陣快速冪啦; 主要是因為a數組能夠獨立出來; 因為系數確定了; 所以能夠用矩陣； 以后看到這種線性齊次遞推式 都能寫個矩陣優化; (我也不知道線性齊次遞推式是什么); f[0][0]=1,f[0][1..m]=0； 最后把f[0][0..m-1]加起來就是答案了; 因為不能全部匹配到嘛. 下面這一段感覺寫得很好吧。
/*f[i][j]的準確含義：1.f[i][j]表示的每種方案不僅與其后j位有關，還應保證不含不吉利數 2.為避免重復，f[i][j]表示的每種方案都不含長度大于j且與不吉利數的前綴相同 的后綴 否則就會出現：從1到m標號，不吉利數為123124時，f[i][2]計數的方案包含f[i][5]計數的方案 的情況 */【完整代碼】
#include <bits/stdc++.h>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%lld",&x)typedef pair<int,int> pii;typedef pair<LL,LL> pll;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int M = 30;struct juzhen{ int s[M][M]; juzhen() { memset(s,0,sizeof s); }};int n,m,mod,f[M],cf[300];char s[M];juzhen a,F;juzhen cheng(juzhen A,juzhen B){ juzhen c; rep1(i,0,m) rep1(j,0,m) rep1(k,0,m) c.s[i][j] = (c.s[i][j]+A.s[i][k]*B.s[k][j])%mod; return c;}juzhen ksm(juzhen A,int n){ if (n==1) return A; juzhen res = ksm(A,n>>1); juzhen t = cheng(res,res); if (n&1) t = cheng(t,A); return t;}int main(){ //freopen("F://rush.txt","r",stdin); rei(n),rei(m),rei(mod); scanf("%s",s+1); f[1] = f[2] = 1; rep1(i,2,m-1) { int j = f[i]; while (j > 1 && s[i]!=s[j]) j = f[j]; f[i+1] = (s[i]==s[j])?j+1:1; } int sum; rep1(i,0,m-1) { int j = i+1; sum = a.s[i][j] = 1; cf[s[j]] = i+1; while (j > 1) { j = f[j]; if (cf[s[j]]!=i+1) { cf[s[j]] = i+1; a.s[i][j] = 1; sum++; } } a.s[i][0] = 10-sum; } F.s[0][0] = 1; F = cheng(F,ksm(a,n)); int ans = 0; rep1(i,0,m-1) ans = (ans + F.s[0][i])%mod; printf("%d/n",ans); return 0;}新聞熱點
疑難解答
