容易看出是道DP
考虑一位一位填数字
设 f [ i ] [ j ] 表示填到第 i 位，在不吉利串上匹配到第 j 位时不出现不吉利数字的方案数
设 g [ i ] [ j ] 表示不吉利串匹配到第 i 位，再添加一个数字，使串匹配到第 j 位的方案数
那么方程显然为 ：
注意我们不需要考虑 $j=m$ 的情况，因为 $j=m$时肯定已经出现匹配了
显然我们可以预处理出 g ，然后直接转移
最后答案就是
还有一个问题，n 太大了
发现 g 是固定的，把 g 搞成矩阵直接矩阵加速一下
复杂度$ O（log_n）$
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<iostream> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=27; int n,m,mo; inline int fk(int x) { return x>=mo ? x-mo : x; } int a[N],fail[N]; char s[N]; int g[N][N]; struct matrix//矩阵不解释 { int a[N][N]; matrix () { memset(a,0,sizeof(a)); } inline matrix operator * (const matrix &tmp) const { matrix res; for(int i=0;i<m;i++) for(int j=0;j<m;j++) for(int k=0;k<m;k++) res.a[i][j]=fk(res.a[i][j]+a[i][k]*tmp.a[k][j]%mo); return res; } }F,M; inline matrix ksm(matrix x,int y)//矩阵快速幂不解释 { matrix res; for(int i=0;i<=m;i++) res.a[i][i]=1; while(y) { if(y&1) res=res*x; x=x*x; y>>=1; } return res; } inline void pre()//预处理，本人闲的蛋疼用kmp预处理g { int x=0; fail[0]=-1; for(int i=1;i<=m;i++) { x=fail[i-1]; while(x!=-1&&a[x+1]!=a[i]) x=fail[x]; fail[i]=x+1; } fail[0]=0; for(int i=0;i<m;i++) for(int j=0;j<10;j++)//枚举填的每个数字，看看能匹配到哪里 { x=i; while(x&&a[x+1]!=j) x=fail[x]; g[i][a[x+1]==j ? x+1 : x]++;//把匹配到的位置++ } for(int i=0;i<m;i++) for(int j=0;j<m;j++) M.a[i][j]=g[i][j];//转移矩阵就是g } int main() { n=read(); m=read(); mo=read(); scanf("%s",s+1); for(int i=1;i<=m;i++) a[i]=s[i]-‘0‘; a[m+1]=a[0]=-1;//闲的蛋疼，就是爱转数字 pre(); F.a[0][0]=1;//初始状态 F=F*ksm(M,n); int ans=0; for(int i=0;i<m;i++) ans=fk(ans+F.a[0][i]); printf("%d",ans); return 0; }
原文：https://www.cnblogs.com/LLTYYC/p/9907548.html