BZOJ_1009_[HNOI2008]GT考试_KMP+矩阵乘法
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
4 3 100
111
111
Sample Output
81
设F[i][j]表示长度为i的串，已经和模式串匹配到第j位有多少种方案。
然后枚举第i位是啥，转移就是F[i-1][k]->F[i][j]，k为加入第i位前在模式串中匹配到哪一位。
其中(k,j)可以用KMP求出(其实暴力找下一位匹配的位置就可以)
同时要保证不能匹配到最后一位，即j不能为m。
然后用矩阵乘法加速这个转移过程。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int mod,n,m,nxt[25];
char s[25];
struct Mat {
int v[21][21];
Mat(){memset(v,0,sizeof(v));}
Mat operator*(const Mat &x)const {
Mat re;int i,j,k;
for(i=0;i<=m;i++) {
for(j=0;j<=m;j++) {
for(k=0;k<=m;k++) {
(re.v[i][j]+=v[i][k]*x.v[k][j]%mod)%=mod;
}
}
}
return re;
}
};
void print(Mat w) {
int i,j;
for(i=0;i<=m;i++) {
for(j=0;j<=m;j++) {
printf("%d ",w.v[i][j]);
}puts("");
}
}
Mat qp(Mat x,int y) {
Mat I;
int i;
for(i=0;i<=m;i++) I.v[i][i]=1;
while(y) {
if(y&1) I=I*x;
x=x*x;
y>>=1;
}
return I;
}
void getnxt() {
int i=0,j=-1;
nxt[0]=-1;
while(i<m) {
if(j==-1||s[i]==s[j]) nxt[++i]=++j;
else j=nxt[j];
}
}
int main() {
scanf("%d%d%d%s",&n,&m,&mod,s);
int i,j,k;
getnxt();
Mat x,ans;
for(i=0;i<m;i++) {
for(j=0;j<=9;j++) {
k=i;
while(k!=-1&&s[k]-'0'!=j) k=nxt[k];
x.v[i][k+1]++;
}
}
ans.v[0][0]=1;
ans=ans*qp(x,n);
int sum=0;
for(i=0;i<m;i++) sum=(sum+ans.v[0][i])%mod;
printf("%d\n",sum);
}