[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\n",ans);

	return 0;

}

巴特西

[HNOI2008]GT考试题解

最新文章

热门文章

巴特西

[HNOI2008]GT考试 题解

最新文章

热门文章

[HNOI2008]GT考试题解