GT考试
题目描述
阿申准备报名参加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
Sample Output
81
solution
我们可以把准考证号看做字符串，这就成了一个求不包含模式串的匹配串的个数的问题。虽然只有一个模式串，我们还是可以对它构造AC自动机，危险结点不可以经过。这样子问题就成了在一张有向图上从起点出发走n步，不经过危险结点的路径条数。观察到n非常大，而m非常小，所以可以用邻接矩阵存储trie图，然后把邻接矩阵n次方，用快速幂优化，就可以解决了
code：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
int ans,n,m,k,num,x,son[1000005][10],head,tail,p,que[1000005],hz[1000005];
struct matrix{int n,a[205][205];
}G;
matrix operator * (matrix a,matrix b){matrix c;c.n=a.n;for(int i=1;i<=a.n;i++)for(int j=1;j<=b.n;j++){c.a[i][j]=0;for(int k=1;k<=b.n;k++)c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%p;}return c;
}
matrix power(matrix a,int b){matrix ans;ans.n=a.n;for(int i=1;i<=ans.n;i++)ans.a[i][i]=1;for(;b;b>>=1,a=a*a)if(b&1)ans=ans*a;return ans;
}
char st[100];
int main(){scanf("%d%d%d",&n,&m,&p);scanf("%s",st);num=1;x=1;for(int i=0;i<m;i++)x=son[x][st[i]-'0']=++num;tail=0;for(int i=0;i<=9;i++)if(son[1][i]){hz[son[1][i]]=1;que[++tail]=son[1][i];}elseson[1][i]=1;while(head<=tail){int u=que[head++];for(int i=0;i<=9;i++)if(son[u][i]){hz[son[u][i]]=son[hz[u]][i];que[++tail]=son[u][i];}elseson[u][i]=son[hz[u]][i];}G.n=num-1;for(int i=1;i<num;i++)for(int j=0;j<=9;j++)if(son[i][j]!=x)G.a[i][son[i][j]]++;G=power(G,n);for(int i=1;i<num;i++)if(i!=x)ans=(ans+G.a[1][i])%p;printf("%d\n",ans);return 0;
}