[CTSC2006] 歌唱王国

\(\text{Problem}:\)[CTSC2006] 歌唱王国

\(\text{Solution}:\)

引入概率生成函数 \(\text{PGF}\)，其 \(i\) 次项的系数是随机变量 \(X\) 等于 \(i\) 的概率，有：

\[F(x)=\sum\limits_{i=0}^{\infty}P(X=i)x^{i} \]

\(\text{PGF}\) 有两个非常重要的性质：

\(F(1)=1\)。各项系数之和即概率之和为 \(1\)。
\(F'(1)=E(X)\)。\(F'(x)=\sum\limits_{i=1}^{\infty}iP(X=i)x^{i-1}\)。各项系数之和即为 \(X\) 的期望。

回到本题。设随机变量 \(X\) 表示随机了 \(X\) 个字符出现了字符串 \(S\)，引入 \(F(x)\) 和 \(G(x)\) 表示：

\[F(x)=\sum\limits_{i=0}^{\infty}P(X=i)x^{i}\\ G(x)=\sum\limits_{i=0}^{\infty}P(X>i)x^{i} \]

利用概率相关知识，易推导得出 \(F(x)\) 与 \(G(x)\) 的关系式：

\[\begin{aligned} F(x)+G(x)&=xG(x)+1\\ F(x)&=(x-1)G(x)+1\\ F'(x)&=G(x)+(x-1)G'(x) \end{aligned} \]

要求的是 \(F'(1)=G(1)\)。

设 \(H(x)\) 的第 \(i\) 项系数表示随机了 \(i\) 个字符还没有出现字符串 \(S\)，再在后面拼接上字符串 \(S\) 的概率。设字符集大小为 \(m\)，根据定义，有：

\[H(x)=G(x)\times (\frac{x}{m})^{\lvert S\rvert} \]

但是由于 \(\text{border}\) 的存在，在拼接字符串 \(S\) 时可能会提前出现字符串 \(S\)。故有：

\[H(x)=\sum\limits_{i=1}^{\lvert S\rvert}[S[1:i] \text{ is a border}]\times F(x)\times (\frac{x}{m})^{\lvert S\rvert-i} \]

将 \(x=1\) 代入，由 \(\text{PGF}\) 的性质，有：

\[E(X)=F'(1)=G(1)=\sum\limits_{i=1}^{\lvert S\rvert}[S[1:i]\text{ is a border}]m^{i} \]

可以利用 \(\text{KMP}\)，哈希等算法在 \(O(\lvert S\rvert)\) 的时间复杂度内求出 \(S\) 的所有 \(\text{border}\)。总时间复杂度 \(O(\sum m)\)。

\(\text{Code}:\)

#include <bits/stdc++.h>
#pragma GCC optimize(3)
//#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
#define vi vector<int>
#define vpi vector<pair<int,int>>
using namespace std; const int N=200010, B1=137, M1=998244353, B2=191, M2=1e9+9, Mod=1e4;
inline int read()
{
	int s=0, w=1; ri char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
	return s*w;
}
int n,T,m,a[N];
int pw1[N],pw2[N];
int hsh1[N],hsh2[N];
inline pair<int,int> Hash(int x,int y)
{
	int w1=(hsh1[y]-1ll*hsh1[x-1]*pw1[y-x+1]%M1+M1)%M1;
	int w2=(hsh2[y]-1ll*hsh2[x-1]*pw2[y-x+1]%M2+M2)%M2;
	return mk(w1,w2);
}
signed main()
{
	n=read(), T=read();
	pw1[0]=pw2[0]=1;
	for(ri int i=1;i<N;i++) pw1[i]=1ll*pw1[i-1]*B1%M1, pw2[i]=1ll*pw2[i-1]*B2%M2;
	for(ri int i=1;i<=T;i++)
	{
		m=read();
		for(ri int j=1;j<=m;j++) a[j]=read();
		for(ri int j=1;j<=m;j++)
		{
			hsh1[j]=(1ll*hsh1[j-1]*B1%M1+a[j])%M1;
			hsh2[j]=(1ll*hsh2[j-1]*B2%M2+a[j])%M2;
		}
		int ans=0;
		for(ri int j=1,now=n%Mod;j<=m;j++,now=1ll*now*n%Mod)
		{
			if(Hash(1,j)==Hash(m-j+1,m))
			{
				ans=(ans+now)%Mod;
			}
		}
		if(ans<1000) printf("0");
		if(ans<100) printf("0");
		if(ans<10) printf("0");
		if(ans<1) printf("0");
		printf("%d\n",ans);
	}
	return 0;
}

[CTSC2006] 歌唱王国

推荐阅读