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<=1000Output
阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果.Sample Input
4 3 100 111 Sample Output 81分析：
第一眼：这难道不是一道数位dp吗 f[i][j][k][0/1][0/1][0/1][0/1] 第i位，添的数字是j，和模式串的第k位相不相同[0/1]，模式串的1~k-1位是不是都匹配上了，1~i位中有没有模式串，卡不卡上界一看数据范围，数位dp就等着吔shi吧。。。
所以这又是一道dp 暴力dp的话，和一样在构建AC自动机的时候，
有一个语句是普通的AC自动机不具有的for (i=0;i<=9;i++) if (!ch[0][i]) ch[0][i]=++tot;
这样在之后是有用的
N的范围使我们不得不考虑优化，因为只有一个字符串
每个状态都是由固定的几个转移而来的，这就让我们想到了矩阵优化那我们就要来构造矩阵了
首先明确状态转移方程： f[i][j] 表示匹配到i位置，在AC自动机上的j节点 f[i][j]向i+1转移，枚举0~9，如果下一个节点不是ed节点 那么我们就可以继续转移现在我们就要构造一个tot（AC自动机上的节点数量）*tot的矩阵
H[当前点][可以转移点]=1 这时AC自动机中看似多余的语句，就起了作用了： 任何不存在于M中的数字都可以看作是根节点
说实话，f[1]的初始化我是看不大懂的
最后的答案实际上就是在H矩阵自乘完之后，再乘上一个f[1] 把值都加起来for (int i=1;i<=tot;i++){ t[i]=0; for (int j=1;j<=tot;j++) t[i]=(t[i]+f[1][j]*ans.H[j][i]%p)%p; sum=(sum+t[i])%p;} 
tip
在KSM的时候，只用自乘n-1次，因为f[1]我们已经处理出来了
所有需要循环AC自动机节点的地方，都是从1开始的
除了在处理f[1]的时候：
//这里写代码片#include#include #include #define ll long longchar s[30];int q[1010],tou,wei,fail[1010],ch[300][30],tot=0,f[2][1001];bool ed[1010];int p,n,m,k;struct node{ int H[100][100]; node operator *(const node &a)const { node ans; for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++) { ans.H[i][j]=0; for (int k=1;k<=tot;k++) ans.H[i][j]=(ans.H[i][j]+H[i][k]*a.H[k][j]%p)%p; } return ans; } void print(node ans) { for (int i=1;i<=tot;i++) { for (int j=1;j<=tot;j++) printf("%d ",ans.H[i][j]); printf("\n"); } } void clear() { memset(H,0,sizeof(H)); } node KSM(int pp) { node a=(*this),an=(*this); pp--; while (pp) { if (pp&1) an=an*a; a=a*a; pp>>=1; } return an; }};node H,ans;void insert(){ int i,now=0; for (i=0;i