沙洋建设局网站,文军seo,广州网站快速制作,焦作建设网站描述 http://www.lydsy.com/JudgeOnline/problem.php?id1009 字符串全部由0~9组成,给出一个串s,求一个长度为n的串,不包含s的种类有多少. 分析 第一眼以为是组合.然后更滑稽的是用错误的方法手算样例居然算出来是对的...我数学是有多差... 题解也是看了好半天,有点难理解. 感觉…描述 http://www.lydsy.com/JudgeOnline/problem.php?id1009 字符串全部由0~9组成,给出一个串s,求一个长度为n的串,不包含s的种类有多少. 分析 第一眼以为是组合.然后更滑稽的是用错误的方法手算样例居然算出来是对的...我数学是有多差... 题解也是看了好半天,有点难理解. 感觉PoPoQQQ神犇讲得还是比较清楚的.传送门:http://blog.csdn.net/popoqqq/article/details/40188173 我们用dp[i][j]表示 : 长度为i的串, 其长度为j的后缀 与 s长度为j的前缀 完全匹配的种类数. 这样的话最后的答案就是anssigma{dp[n][i]}(0im). 这里还有一个二维的a数组,就这个比较难解释... dp[i][y]可以由dp[i-1][x]转移而来,那么匹配的s的前缀由长度x变成了长度y,a[x][y]表示的就是在结尾添加一个字符后,匹配长度从x变成y,这样的字符有多少种. 那么 dp[i][y]sigma{dp[i-1][x]*a[x][y]}. 这个可以用矩阵乘法算. 那么a数组怎么求呢?用kmp. a[x][y]表示的是前缀匹配长度由x变成了y的种类数,那么从每一位i开始匹配,如果匹配到了j,那么a[i][j1](数组从0开始,第i位之前匹配了i个,匹配到第j位,应该是j1个). p.s.我好菜呀... 1 #include bits/stdc.h2 using namespace std;3 4 const int maxn1005;5 int n,m,p,ans;6 char str[maxn];7 int f[maxn];8 9 struct matrix{
10 int x[25][25];
11 matrix(){ memset(x,0,sizeof x); }
12 int * operator [] (int id){ return x[id]; }
13 }dp,a;
14 void operator * (matrix x,matrix y){
15 matrix z;
16 for(int i0;im;i)for(int j0;jm;j)for(int k0;km;k)
17 z[i][j]x[i][k]*y[k][j], z[i][j]%p;
18 xz;
19 }
20 void kmp(){
21 for(int i1;im;i){
22 int jf[i];
23 while(jstr[i]!str[j]) jf[j];
24 f[i1]str[i]str[j]?j1:0;
25 }
26 for(int i0;im;i)for(char k0;k9;k){
27 int ji;
28 while(jk!str[j]) jf[j];
29 if(kstr[j]) a[i][j1];
30 else a[i][0];
31 }
32 }
33 void quick_power(int y){
34 for(;y;a*a,y1) if(y1) dp*a;
35 }
36 int main(){
37 scanf(%d%d%d,n,m,p);
38 scanf(%s,str);
39 kmp();
40 dp[0][0]1;
41 quick_power(n);
42 for(int i0;im;i) ansdp[0][i], ans%p;
43 printf(%d\n,ans);
44 return 0;
45 } View Code 1009: [HNOI2008]GT考试 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 2815 Solved: 1738[Submit][Status][Discuss] Description 阿申准备报名参加GT考试准考证号为N位数X1X2....Xn(0Xi9),他不希望准考证号上出现不吉利的数字。 他的不吉利数学A1A2...Am(0Ai9)有M位不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为 0 Input 第一行输入N,M,K.接下来一行输入M位的数。 N10^9,M20,K1000 Output 阿申想知道不出现不吉利数字的号码有多少种输出模K取余的结果. Sample Input 4 3 100 111 Sample Output 81 HINT Source转载于:https://www.cnblogs.com/Sunnie69/p/5554726.html
