1009: [HNOI2008]GT考试
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 4309 Solved: 2640
[Submit][Status][Discuss]
Description
阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。
他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为
0
Input
第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000
Output
阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果.
Sample Input
Sample Output
分析：
开始做我最弱的字符串题目了。。。
题目很显然是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 <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
int fail[][],n,m,mod,next[];
struct fi{
int data[][];
}A,T;
char str[];
void get_Fail(){
scanf("%s",str);
for(int i = ,j = ;i < m;i++){
while(j && str[i] != str[j])j = next[j - ];
if(str[i] == str[j])j++;
next[i] = j;
}
memset(T.data,,sizeof T);
for(int i = ;i < m;i++){
for(int j = ;j <= ;j++){
int k = i;
while(k && str[k] - '' != j)k = next[k - ];
if(j == str[k] - '')T.data[i][k + ]++;
else T.data[i][]++;
}
}
memset(A.data,,sizeof A.data);
for(int i = ;i < m;i++)A.data[i][i] = ;
}
fi operator * (const fi & c,const fi & d){
fi t;
for(int i = ;i < m;i++){
for(int j = ;j < m;j++){
t.data[i][j] = ;
for(int k = ;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 & )A = A * T;
k >>= ;
T = T * T;
}
}
int main(){
scanf("%d %d %d",&n,&m,&mod);
get_Fail();
cmd(n);
int ans = ;
for(int i = ;i < m;i++)(ans += A.data[][i]) %= mod;
printf("%d\n",ans); }