矩阵快速幂 + DP + KMP－GT考试－AcWing 1305_综合

矩阵快速幂 + DP + KMP－GT考试－AcWing 1305

$阿申准备报名参加 GT 考试，准考证号为 n 位数 X_1X_2?X_n，他不希望准考证号上出现不吉利的数字。$

$他的不吉利数字 A_1A_2?A_m 有 m 位，不出现是指 X_1X_2?X_n 中没有恰好一段等于 A_1A_2?A_m，A_1 和 X_1 可以为 0。$

输入格式

第一行输入 n,m,K。

接下来一行输入 m 位的不吉利数字。

输出格式

阿申想知道不出现不吉利数字的号码有多少种，输出模 K 取余的结果。

数据范围

$0≤Xi,Ai≤9, 1≤n≤10^9, 1≤m≤20, 2≤K≤1000$

输入样例：

4 3 100 
111

输出样例：

分析：

$我们将不吉利数字看作一个长度为m的字符串S，准考证号为长度为n的字符串P_n，$

$将问题转化为类似于字符串匹配的问题。$

$本题类似于：本题类似于：$ DP + KMP - 状态机模型 - IndeedTokyo2019校招笔试题 - 设计密码

状态表示:

$f[i][j]：所有长度为i，且不包含S串，且后缀部分与S的前缀部分匹配的长度为j的所有字符串P_i的集合。$

$我们向枚举的字符串P_i末尾添加新的字符c，得到P_{i+1}，$

$接着计算P_{i+1}的后缀与S的前缀匹配的最大长度，假设是k，则更新f[i+1][k]+=f[i][j]，$

$字符c可取0到9十种数字，对每一个P_i，共枚举10种不同的P_{i+1}，$

$我们能够得到数组f的第i层和第i+1层的递推关系:$

$f[i+1][k]=a_{j0}f[i][0]+a_{j1}f[i][1]+a_{j2}f[i][2]+...+a_{jk}f[i][k]+...+a_{jm-1}f[i][m-1]$

$其中，a_{jk}表示：给P_i添加字符c后，P_{i+1}的后缀与S的前缀匹配的最大长度从j变为k的方案数量。$

$于是，我们根据f[i+1]与f[i]的递推关系，可以设变换矩阵A_{m×10}，求出方案总和res=\sum_{i=0}^{m-1}f[n][i]$

具体步骤：

$①、KMP预处理变换矩阵A_{m×10}$

$②、矩阵快速幂求A^n$

$③、f[n]=f[0]A^n$

边界的处理:

$设置f[0]=1，需要能够正确计算边界f[1]。$

代码：

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N=25;int n,m,mod;
char str[N];
int ne[N];
int a[N][N];
int f0[N][N];void get_next()
{for(int i=2,j=0;i<=m;i++){while(j&&str[i]!=str[j+1]) j=ne[j];if(str[i]==str[j+1]) j++;ne[i]=j;}
}void kmp()
{for(int j=0;j<m;j++)for(char 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]++;}
}void mul(int a[][N],int b[][N])
{int c[N][N]={0};for(int i=0;i<m;i++)for(int j=0;j<m;j++)for(int k=0;k<m;k++)c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;memcpy(a,c,sizeof c);
}void quick_pow(int a[][N],int k)
{int E[N][N];memset(E,0,sizeof E);for(int i=0;i<m;i++) E[i][i]=1;f0[0][0]=1;while(k){if(k&1) mul(E,a);mul(a,a);k>>=1;}memcpy(a,E,sizeof E);
}int main()
{cin>>n>>m>>mod;cin>>str+1;get_next();kmp();quick_pow(a,n);mul(f0,a);int res=0;for(int i=0;i<m;i++) res=(res+f0[0][i])%mod;cout<<res<<endl;return 0;
}