洛谷P3193 GT考试 kmp+矩阵优化dp

题意

• 求(N)位数字序列（可以有前导0）中不出现某(M)位子串的个数，模(K)。
• (N<=10^9,M<=20,K<=1000)

分析

设(dp[i][j])表示匹配串下标(i)匹配到模式串下标(j)时，满足要求的方案数；枚举匹配串的下一位是0~9中哪个数，若原先匹配串最远能匹配到模式串的下标为(k)，加入这个数后最远能匹配到模式串的下标为(j)，设(a[k][j])为将匹配模式串下标从(k)变为(j)的数字个数，可以用(next)数组求出，dp转移方程就变成了

[dp[i][j]=sum_{k=0}^{m-1}dp[i][k]*a[k][j] ]

这个式子可以用矩阵优化。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=1e5+10;
int n,m,p,nex[21];
char s[21];
ll a[20][20],ret[20][20];
int find(int j,char k){
	while(j&&s[j+1]!=k) j=nex[j];
	if(k==s[j+1]) ++j;
	return j;
}
void mul(ll a[20][20],ll b[20][20]){
	ll tmp[20][20]={0};
	for(int i=0;i<m;i++)
	for(int j=0;j<m;j++)
	for(int k=0;k<m;k++)
	tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j]%p)%p;
	for(int i=0;i<m;i++) for(int j=0;j<m;j++) a[i][j]=tmp[i][j];
}
void ksm(ll b){
	for(int i=0;i<m;i++) ret[i][i]=1;
	while(b){
		if(b&1) mul(ret,a);
		mul(a,a);
		b>>=1;
	}
}
int main(){
	//ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	scanf("%d%d%d",&n,&m,&p);
	scanf("%s",s+1);
	for(int i=2,j=0;i<=m;i++){
		while(j&&s[i]!=s[j+1]) j=nex[j];
		if(s[i]==s[j+1]) ++j;
		nex[i]=j;
	}
	for(int j=0;j<m;j++){
		for(char k='0';k<='9';k++){
			a[j][find(j,k)]++;
		}
	}ksm(n);
	ll ans=0;
	for(int i=0;i<m;i++){
		ans=(ans+ret[0][i])%p;
	}
	printf("%lld
",ans);
	return 0;
}