301045 / 雷的打字机

雷靠当妈妈的间谍得到了一台精致的打字机。菲尔对这台打字机充满了好奇。
一天，他开始捣鼓这台打字机。这台打字机上有 n 个按键，每个按键对应一个字符，且这 n 个字符两两不同。每次按下一个按键时，打字机就会打印出一个对应的字符。打印出的字符顺次连接可以得到一个打印出的字符串。
菲尔不想用这台打字机写什么文章。每次他有 $p_i$ 的概率按下第 i 个按键，当打印出的字符串存在任意一个长度为偶数的回文子串时，他就会停止按按键。他想知道，打印出的字符串的期望长度是多少。

如果你回答不出来的话，菲尔就只好去问诺曼咯。

p 数组是随机生成的，随机种子为 seed 。具体的生成方式为：（C / C++ 代码）

int p[10000011], n; namespace Generator {     unsigned int seed;     int Rand() {         seed = (seed << 2) ^ (seed >> 5) ^ (seed << 7) ^ (seed >> 11);         return seed % 998244353;     }     void Generate() {         int sum = 0;         for (int i = 1; i < n; ++i) {             p[i] = Rand();             sum = (sum + p[i]) % 998244353;         }         p[n] = (998244354 - sum) % 998244353;     } }

C / C++ 选手可以选择复制该代码段到你的程序中。在读入 n 以及 Generator::seed 后，调用 Generator::Generate() 即可生成 p 数组。
该段代码的意义是，读入 seed 之后， $p_1$ 至 $p_{n-1}$ 这 n-1 个数依次由 Rand() 生成。为使总概率等于 1 ， $p_n$ 等于 $\displaystyle \left(1 - \sum_{1 \le i < n} p_i \right)\bmod 998244353$ 。注意此处 seed 是 unsigned int 类型，生成所得的 p 数组是在模 998244353 意义下的。

输出仅一行，包含一个整数，表示答案。你需要输出答案在模 998244353 意义下的值。
即设答案化为最简分式后的形式为 $\frac{a}{b}$ ，其中 a 和 b 互质。输出整数 x 使得 $bx \equiv a \bmod 998244353$ 且 $0 \le x < 998244353$ 。可以证明这样的整数 x 是唯一的。

#include<cstdio> #include<algorithm> using namespace std; const int N=1e7+5; const int mod=998244353; int n,p[N],sum,pre[N],inv[N],ans; unsigned int seed; int rng(){ seed=(seed<<2)^(seed>>5)^(seed<<7)^(seed>>11); return seed%mod; } int fastpow(int a,int b){ int res=1; while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;} return res; } int main(){ scanf("%d%u",&n,&seed); for(int i=1;i<n;++i) p[i]=rng(),sum=(sum+p[i])%mod; p[n]=mod+1-sum; for(int i=pre[0]=1;i<=n;++i)pre[i]=1ll*pre[i-1]*(1+p[i])%mod; pre[n]=fastpow(pre[n],mod-2); for(int i=n;i;--i){ inv[i]=1ll*pre[i]*pre[i-1]%mod; pre[i-1]=1ll*pre[i]*(1+p[i])%mod; } for(int i=1;i<=n;++i)ans=(ans+1ll*p[i]*p[i]%mod*inv[i])%mod; printf("%d\n",fastpow(ans,mod-2));return 0; }

#include<bits/stdc++.h> using namespace std; #define ll long long #define P 998244353 int n,i,s,a1,a2,y,z,ans; unsigned int seed; int Pow(int x,int y) { int s=1; for(;y;y>>=1,x=(ll)x*x%P)if(y&1)s=(ll)s*x%P; return s; } void work(int x) { y=(ll)x*x%P; z=x+1; if(z==P)z=0; a1=((ll)a1*z+(ll)a2*y)%P; a2=(ll)a2*z%P; s+=x; if(s>=P)s-=P; } int main() { cin>>n>>seed; a1=0; a2=1; while(--n) { seed=(seed<<2)^(seed>>5)^(seed<<7)^(seed>>11); work(seed%P); } work((P+1-s)%P); ans=(ll)a2*Pow(a1,P-2)%P; cout<<ans<<endl; return 0; }

详情