【题目链接】: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;}新闻热点
疑难解答
