[HNOI2008]GT考试 题解

这题比较难搞。考虑设计状态：(f_{i,j}) 表示当前考虑到 (X_i) 位，且 (X) 的后 (j) 位刚好与 (A) 列匹配时的方案数。最终答案为 (sum_{i=0}^{m-1}f_{n,i})。
接下来考虑如何转移，如果我们以外层位置作为状态，则必然是从 (f_{i-1}) 转移到 (f_i) 来，我们需要枚举最后一位进行转移，但枚举最后一位对内层循环却不太好控制，因为我们不太清楚它的匹配长度到底是多少。所以转化思路，另设 (g_{i,j}) 表示在 (X) 的后 (i) 位与 (A) 列匹配的情况下，有多少种加数字的方法使得匹配长度变为 (j)，这么做可以使 (g) 只与 (A) 列有关，能够预处理出来。
那么转移方程：

[f_{i,j}=sum_{k=0}^{m-1}f_{i-1,k}g_{k,j} ]

由于 (n) 比较大，又发现这个式子长得很像矩阵乘法的式子，故可以快速幂递推。即

[F_i=[f_{i,0} f_{i,1} dots f_{i,m-1}]=F_{i-1}G,F_n=F_0G^n ]

代码还是挺好写的

#include <bits/stdc++.h>
using namespace std;

const int N=25;
int n,m,djq,nxt[N],g[N][N],f[N][N],res[N][N],ans;
char s[N];

void mul(int a[N][N],int b[N][N])
{
	static int c[N][N];
	memset(c,0,sizeof(c));
	for(int i=0;i<m;++i)
		for(int j=0;j<m;++j)
			for(int k=0;k<m;++k)
				(c[i][j]+=a[i][k]*b[k][j])%=djq;
	memcpy(a,c,sizeof(c));
}

int main()
{
	scanf("%d%d%d %s",&n,&m,&djq,s+1);
	for(int i=2,j=0;i<=m;++i)
	{
		while(j&&s[i]!=s[j+1]) j=nxt[j];
		if(s[i]==s[j+1]) ++j;
		nxt[i]=j;
	}
	for(int i=0;i<m;++i)
		for(char j='0';j<='9';++j)
		{
			int k=i;
			while(k&&s[k+1]!=j) k=nxt[k];
			if(s[k+1]==j) ++k;
			++g[i][k];
		}
	for(int i=0;i<m;++i) res[i][i]=1;
	for(;n;n>>=1,mul(g,g))
		if(n&1) mul(res,g);
	f[0][0]=1; mul(f,res);
	for(int i=0;i<m;++i) (ans+=f[0][i])%=djq;
	printf("%d
",ans);
	return 0;
}