描述
字符串全部由0~9组成,给出一个串s,求一个长度为n的串,不包含s的种类有多少.
分析
第一眼以为是组合.然后更滑稽的是用错误的方法手算样例居然算出来是对的...我数学是有多差...
题解也是看了好半天,有点难理解.
感觉PoPoQQQ神犇讲得还是比较清楚的.传送门:
我们用dp[i][j]表示 : 长度为i的串, 其长度为j的后缀 与 s长度为j的前缀 完全匹配的种类数.
这样的话最后的答案就是ans=sigma{dp[n][i]}(0<=i<m).
这里还有一个二维的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][j+1]++(数组从0开始,第i位之前匹配了i个,匹配到第j位,应该是j+1个).
p.s.我好菜呀...
1 #include2 using namespace std; 3 4 const int maxn=100+5; 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 i=0;i >=1) if(y&1) 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 i=0;i
1009: [HNOI2008]GT考试
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 2815 Solved: 1738[][][]Description
阿申准备报名参加GT考试,准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。
他的不吉利数学A1A2...Am(0<=Ai<=9)有M位,不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为 0Input
第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000
Output
阿申想知道不出现不吉利数字的号码有多少种,输出模K取余的结果.
Sample Input
4 3 100 111
Sample Output
81