题目描述

阿申准备报名参加 GT 考试，准考证号为 n 位数 X1X2⋯Xn(0≤Xi≤9)，他不希望准考证号上出现不吉利的数字。

他的不吉利数字 A1A2⋯Am(0≤Ai≤9) 有 m 位，不出现是指 X1X2⋯Xn 中没有恰好一段等于 A1A2⋯Am ，A1和 X1 可以为 0。

样例

4 3 100 
111

81

本题是dp和kmp和qmi的结合体
理解的时候有点麻烦，这里给出样例111的a矩阵进行分析
a[3][3]={
{9,1,0}
{9,0,1}
{9,0,0}
};
这里的a[i][j]表示从最大匹配前缀为i转化为最大匹配前缀为j的方案数,具体代码在下面

   for(int j=0;j<m;j++)
    //以样例111为例子
    //枚举m位数的所有情况比如j=0,c='1'
    //会得到你a[0][1]=1,也就是从最大匹配长度0，转到1的方案加1
    //然后一轮结束后会有a[0][0]=9,也就是从最大匹配长度0，转到0的方案加9
    //第二轮j=1,则会有a[1][2]=1,a[1][0]=9,第三轮会有a[2][2]=0,a[2][0]=9;
        for(int c='0';c<='9';c++)
        {
            int k=j;
            while(k&&str[k+1]!=c)   k=ne[k];
            if(str[k+1]==c) k++;
            if(k<m) a[j][k]++;//从与前缀最大匹配长度j
            //转到最大匹配长度k的方案加1
        }

首先要用kmp处理ne数组
然后在用kmp,代码中第一维j表示已经的最大匹配前缀
第二位k表示添上c后匹配的最大长度k,如果添上了一个c后,str[j+1]=='c',
那就k++,表示添加上c后反而使得最大前缀匹配更大了,如果str[j+1]!='c',
说明不能匹配就得用k=ne[k];先更新位置，然后继续看可不可以匹配c,依次类推
于是最后就只要j<m就是转化后的最大匹配长度小于m的方案是可行的就a[j][k]++;

其次就是快速幂了