题目大意：给定长度为m的数字串s，求不包含子串s的长度为n的数字串的数量
n<=10^9 光看这个O(n)就是挂
我们不考虑这个 令f[i][j]为长度为i的数字串中最后j位与s中的前j位匹配的方案数
比如当s为12312时 f[i][3]表示长度为i，以123结尾且不包含子串”12312“的方案数
a[x][y]为f[i-1][x]转移至f[i][y]的方案数
换句话说(可能描述不清楚) a[x][y]为s的长度为x的前缀加上一个数字后 后缀可以与最长长度为y的前缀匹配 这个数字可以有多少种
比如说12312 这个数字串生成的a数组为(数组从0开始)：
9 1 0 0 0 0
8 1 1 0 0 0
8 1 0 1 0 0
9 0 0 0 1 0
8 1 0 0 0 1
a[2][1]=1 表示长度为2的前缀加上一个'1'之后最多与长度为1的前缀匹配
a[4][0]=8 表示长度为4的前缀加上'1''2'以外的数就变成了长度为0的前缀
但是a[x][5]表示完全匹配，不满足要求的题意，所以我们矩阵乘法时不考虑这一列
我们发现f[i-1]乘上这个矩阵就变成了f[i] 这个矩阵怎么求呢？KMP算法，对于每个长度的前缀枚举下一个字符进行转移 具体写法详见代码
f初值是f[0][0]=1,f[0][x]=0 (x>0)
于是最后我们只需要取答案矩阵的第一行即可
去网上找了一堆题解才看懂0.0 这里写的稍微详细一点吧
#include
#include
#include
#include
using namespace std; struct matrix{ int xx[22][22]; int* operator [] (int x) { return xx[x]; } }a,b; int n,m,p,ans; char s[100]; int next[100]; void operator *= (matrix &x,matrix &y) { int i,j,k; matrix z; memset(&z,0,sizeof z); for(i=0;i
>=1; } } int main() { int i; cin>>n>>m>>p; scanf("%s",s+1); KMP(); for(i=0;i