題目

首先看到這個出現長度至少為\(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; }

轉載于:https://www.cnblogs.com/asuldb/p/10950678.html

總結

以上是生活随笔為你收集整理的【牛客挑战赛31D】 雷的打字机的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。