【牛客挑战赛31D】雷的打字机

题目

首先看到这个出现长度至少为\(2\)的回文子串

这就等价于不能出现两个连续且相同的字符

于是我们用概率生成函数来搞

设\(g_i\)表示\(i\)次操作后游戏没有结束的概率，\(f_{i,j}\)表示\(i\)次操作之后出现最后两个字符都是\(j\)的概率，这样的话游戏就结束了

再定义\(f_i=\sum_{j=1}^nf_{i,j}\)

我们要求的东西显然就是\(F'(1)\)，即期望长度

那个非常有用的\(g_i=g_{i+1}+f_{i+1}\)还是成立的

于是

\[xG(x)+1=F(x)+G(x)
\]

代入\(x=1\)，并两边求导

\[G(1)=F'(1)
\]

显然对于任意的\(F_i(x)\)都会存在

\[G(x)p_i^2x^2=F_i(x)p_ix+F_i(x)
\]

就是往一个非结束状态后面强塞两个字符\(i\)，代入\(x=1\)就有

\[G(1)p_i^2=F_i(1)(1+p_i)
\]

\[F_i(1)=\frac{p_i^2}{1+p_i}G(1)
\]

又因为\(\sum_{i=1}^nF_i(1)=1\)，于是\(\sum_{i=1}^n\frac{p_i^2}{1+p_i}G(1)=1\)，于是答案就是

\[\frac{1}{\sum_{i=1}^n\frac{p_i^2}{1+p_i}}
\]

之后发现\(n\leq 10^7\)，带\(log\)求逆元显然不是很可行了

于是离线求一下逆元就可以了，就像十二省联考里的D2T3那样就好了

代码

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define re register

const int mod=998244353;

const int maxn=1e7+5;

int n,ans;unsigned int seed;

int fac[maxn],p[maxn];

inline int Rand() {

	seed=(seed<<2)^(seed>>5)^(seed<<7)^(seed>>11);return seed%mod;

}

inline int ksm(int a,int b) {

	int S=1;

	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) S=1ll*S*a%mod;

	return S;

}

inline void Generate() {

	scanf("%d%u",&n,&seed);

	int sum=0;

	for(re int i=1;i<n;++i)

		p[i]=Rand(),sum=(sum+p[i])%mod;

	p[n]=(mod+1-sum)%mod;

}

int main() {

	Generate();fac[0]=1;

	for(re int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*(p[i]+1)%mod;

	int Inv=ksm(fac[n],mod-2),inv;

	for(re int i=n;i;i--) {

		inv=1ll*Inv*fac[i-1]%mod;

		ans=(ans+1ll*p[i]*p[i]%mod*inv%mod)%mod;

		Inv=1ll*Inv*(p[i]+1)%mod;

	}

	printf("%d\n",ksm(ans,mod-2));

	return 0;

}

巴特西

【牛客挑战赛31D】雷的打字机

最新文章

热门文章

巴特西

【牛客挑战赛31D】 雷的打字机

最新文章

热门文章

【牛客挑战赛31D】雷的打字机