AT4996 [AGC034F] RNG and XOR【异或,期望】

AT4996 [AGC034F] RNG and XOR

设 $e_i$ 表示从 0 走到 $i$ 的期望次数，显然等于 $i$ 走到 0 的期望次数。 $e_i=\{\begin{array}{ll}0,& i=0\\ 1+{\sum }_{j=0}^{2^n-1}{e}_{i\oplus j}\ast p_j,& i\ne 0\end{array}$

设 $E,P$ 分别为 $e_i,p_i$ 的集合幂级数，用异或卷积定义乘法，则有： $E\ast P+I=E+c$ 其中 $c$ 为一个常数，用于修正 $e_0$。

得到 $FWT(E)\ast FWT(P)+FWT(I)=FWT(E)+FWT(c)$ 在 $i$ 处的关系式为：$$FWT(E{)}_i\ast (FWT(P{)}_i-1)=FWT(c{)}_i-FWT(I{)}_i$$ 其中 $FWT(I)=2^n$，$FWT(c)={\sum }_{i=0}^{2^n-1}c{x}^i$ 当 $i=0$ 时，$FWT(P{)}_0=\sum p_i=1$，所以 $c=FWT(I{)}_0=2^n$

对于 $i>1$，$FWT(P{)}_i<S(P)=1$，所以 $FWT(E{)}_i=\frac{2^n}{FWT(P{)}_i-1}$

而 $FWT(E{)}_0$ 利用 $e_0=0=\frac{1}{2^n}{\sum }_{j=0}^{2^n-1}FWT(E{)}_j$ 求解。

实际上可以假设 $FWT(E{)}_0=0$ 求出一个答案 $E^{\prime }$，然后实际上 $E_i=E_i^{\prime }+\frac{1}{2^n}FWT(E{)}_0$，所以 $\frac{1}{2^n}FWT(E{)}_0=0-E_0^{\prime }$

求出 $FWT(E)$ 后再变换回来就可以了。

双倍经验：ZJOI2019开关，题解里面最后 $FWT(G{)}_T={\sum }_{i\notin T}{p}_i-{\sum }_{i\in T}{p}_i$ 是因为概率只在单点处有值。

Code：

#include<bits/stdc++.h> #define maxn 300005 using namespace std; const int mod = 998244353; int n,N,p[maxn],E[maxn]; int Pow(int a,int b){int s=1;for(;b;b>>=1,a=1ll*a*a%mod) b&1&&(s=1ll*s*a%mod); return s;} int upd(int x){return x+(x>>31&mod);} void FWT(int *a,int len,int flg){ for(int i=2,l=1,v;i<=len;l=i,i<<=1) for(int j=0;j<len;j+=i) for(int k=j;k<j+l;k++) v=a[k],a[k]=upd(v+a[k+l]-mod),a[k+l]=upd(v-a[k+l]); if(flg^1) for(int i=0,Inv=Pow(len,mod-2);i<len;i++) a[i]=1ll*a[i]*Inv%mod; } int main() { scanf("%d",&n),N=1<<n; int s=0; for(int i=0;i<N;i++) scanf("%d",&p[i]),s=upd(s+p[i]-mod); s=Pow(s,mod-2); for(int i=0;i<N;i++) p[i]=1ll*p[i]*s%mod; FWT(p,N,1); for(int i=1;i<N;i++) E[i]=1ll*N*Pow(upd(p[i]-1),mod-2)%mod; FWT(E,N,-1); int x=mod-E[0]; for(int i=0;i<N;i++) printf("%d\n",upd(E[i]+x-mod)); }