正题
题目链接:https://www.luogu.com.cn/problem/AT4996
题目大意
给出一个\(0\sim 2^n-1\)下标的数组\(p\)，\(p_i\)表示有\(p_i\)的权重概率选择\(i\)。
开始有一个\(x=0\)，每次选择一个数字\(y\)让\(x=x\ xor\ y\)
对于每个\(i\)求期望多久后第一次变成\(i\)。
\(1\leq n\leq 18\)
解题思路
搞一个异或卷积的生成函数，先搞出概率的函数\(P\)。
然后设\(E\)表示答案的函数，那么有
\[E\times P+I=E+c
\]
\(c\)表示余项，\(I(x)=\sum_{i=1}^{\infty}x^i\)
先求出余项\(c\)来，设\(S(A)\)表示生成函数\(A\)的所有系数和
\[S(E)\times S(P)+S(I)=S(E)+c
\]
\(S(P)=1\)，\(S(I)=2^n\)，那我们有\(c=S(I)=2^n\)
所以就有
\[E\times P+I=E+2^n
\]
\[E\times (P-1)=2^n-I
\]
\[FWT(E)=\frac{FWT(2^n-I)}{FWT(P-1)}
\]
然后跑\(FWT\)就好了。
注意跑出来的\(E_0\neq 0\)，我们要把所有的答案减去\(E_0\)
时间复杂度\(O(2^nn)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1<<19,P=998244353;
ll n,k,f[N],g[N];
ll power(ll x,ll b){
ll ans=1;
while(b){
if(b&1)ans=ans*x%P;
x=x*x%P;b>>=1;
}
return ans;
}
void FWT(ll *f,ll op){
for(ll p=2;p<=n;p<<=1){
ll len=(p>>1);
for(ll k=0;k<n;k+=p)
for(ll i=k;i<k+len;i++){
ll x=f[i],y=f[i+len];
f[i]=(x+y)*op%P;
f[i+len]=(x-y+P)*op%P;
}
}
return;
}
signed main()
{
scanf("%lld",&k);n=1<<k;
ll sum=0;
for(ll i=0;i<n;i++){
scanf("%lld",&f[i]);
sum=(sum+f[i])%P;g[i]=P-1;
}
sum=power(sum,P-2);
for(ll i=0;i<n;i++)f[i]=f[i]*sum%P;
g[0]=(g[0]+n)%P;f[0]=(f[0]+P-1)%P;
FWT(f,1);FWT(g,1);
for(ll i=0;i<n;i++)
f[i]=g[i]*power(f[i],P-2)%P;
FWT(f,(P+1)/2);
for(ll i=0;i<n;i++)
printf("%lld\n",(f[i]-f[0]+P)%P);
return 0;
}