1009: [HNOI2008]GT考试
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 4309 Solved: 2640[][][]
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
分析：
开始做我最弱的字符串题目了。。。
题目很显然是dp。定义状态dp[i][j]表示当前串长度为i，后j位是和不吉利串的前j位相同的方案数。
考虑转移：
可以由dp[i - 1][j - 1]转移到 dp[i][j] ----①
可以由dp[i - 1][k]转移到dp[i][j] ----②（k > j）就是说i - 1匹配为k，加个数字不合法了，但现在后j位还是和原字符串有匹配的。这里就需要用KMP的失败指针构造一下了。
可以由dp[i - 1][j]转移到dp[i][0] ----③ 当①和②都不成立，就说明当前和原字符串没任何匹配，转移到0状态.
然后发现n很大，我们转移是O（n * m）的，但每次的转移是线性的，很显然可以用矩乘优化。
最后把0 ~ m - 1加起来就好了。
AC代码：
# include# include # include using namespace std;int fail[23][11],n,m,mod,next[23]; struct fi{ int data[23][23];}A,T;char str[23];void get_Fail(){ scanf("%s",str); for(int i = 1,j = 0;i < m;i++){ while(j && str[i] != str[j])j = next[j - 1]; if(str[i] == str[j])j++; next[i] = j; } memset(T.data,0,sizeof T); for(int i = 0;i < m;i++){ for(int j = 0;j <= 9;j++){ int k = i; while(k && str[k] - '0' != j)k = next[k - 1]; if(j == str[k] - '0')T.data[i][k + 1]++; else T.data[i][0]++; } } memset(A.data,0,sizeof A.data); for(int i = 0;i < m;i++)A.data[i][i] = 1;}fi operator * (const fi & c,const fi & d){ fi t; for(int i = 0;i < m;i++){ for(int j = 0;j < m;j++){ t.data[i][j] = 0; for(int k = 0;k < m;k++){ (t.data[i][j] += c.data[i][k] * d.data[k][j]) %= mod; } } } return t;}void cmd(int k){ while(k){ if(k & 1)A = A * T; k >>= 1; T = T * T; }}int main(){ scanf("%d %d %d",&n,&m,&mod); get_Fail(); cmd(n); int ans = 0; for(int i = 0;i < m;i++)(ans += A.data[0][i]) %= mod; printf("%d\n",ans); }