【杂题】[AGC034F] RNG and XOR【集合幂级数】【FWT】【DP】

Dear 丶 2021-12-23 12:41 160阅读 0赞

## Description ##

你有一个随机数生成器，它会以一定的概率生成\[0,2^N-1\]中的数，每一个数的概率是由序列A给定的，Pi=Ai/sum(Ai)

现在有一个初始为0的数X，每一轮随机生成一个数v，将X变成X xor v  
求X变成0~2^N-1的期望轮数  
答案对998244353取模

N<=18,Ai<=1000

## Solution ##

不妨反过来做，f\[i\]为i到0的期望轮数，显然等价  
易得i>0,  
\\\[f\[i\]=1+\\sum f\[i\\ xor\\ j\]p\[j\]\\\]  
1移到左边来  
\\\[f\[i\]-1=\\sum f\[i\\ xor\\ j\]p\[j\]\\\]  
写成集合幂级数形式就是  
\\\[(f\[0\],f\[1\],f\[2\],...,f\[2^N-1\])\\bigoplus(p\[0\],p\[1\],p\[2\],...,p\[2^N-1\])=(?,f\[1\]-1,f\[2\]-1,...,f\[2^N-1\])\\\]

?是因为f\[0\]不满足转移式

但我们发现\\(\\sum p=1\\)，也就是说卷积过后总和不变  
因此\\(? = f\[0\]+2^N-1\\)

把p\[0\]-1，后面的f就全部消掉

我们做一个逆卷积即可。  
具体来说，把等号右边FWT，乘上中间的FWT再每项逆元的结果，再IFWT回去。

不行。  
我们发现中间集合幂级数的FWT后2^N-1 +(-1)+(-1)+…+(-1)这一项是0（容易证明只有这一项是0），对应的右边也是0，我们无法得到左边这一项的值。

但我们忽略了一个信息，f\[0\]=0  
不妨先假定左边这一项就是0，IFWT回去以后看看f\[0\]差了多少，那就是这一项少贡献了多少，推回去就行了。

时间复杂度O(2^N\*N)

## Code ##

#include <bits/stdc++.h> #define fo(i,a,b) for(int i=a;i<=b;++i) #define fod(i,a,b) for(int i=a;i>=b;--i) #define L 19 #define M 262144 const int mo=998244353; typedef long long LL; using namespace std; int n,m; int a[M+1],b[M+1]; LL ksm(LL k,LL n) { LL s=1; for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo; return s; } const LL ny2=499122177; void FWT(int *a,bool pd) { for(int h=1;h<m;h<<=1) for(int j=0;j<M;j+=h*2) fo(i,0,h-1) { int v=a[i+j+h]; a[i+j+h]=(a[i+j]-v+mo)%mo,a[i+j]=(a[i+j]+v)%mo; if(pd) a[i+j]=(LL)a[i+j]*ny2%mo,a[i+j+h]=(LL)a[i+j+h]*ny2%mo; } } LL pr[M]; int main() { cin>>n; m=1<<n; LL sum=0; fo(i,0,m-1) scanf("%lld",&pr[i]),sum=(sum+pr[i])%mo; sum=ksm(sum,mo-2); a[0]=m-1; fo(i,1,m-1) a[i]=mo-1; fo(i,0,m-1) b[i]=pr[i]*sum%mo; b[0]=(b[0]-1+mo)%mo; FWT(a,0),FWT(b,0); int wz=0; fo(i,0,m-1) { if(b[i]!=0) a[i]=(LL)a[i]*ksm(b[i],mo-2)%mo; else a[i]=0,wz=i; } FWT(a,1); LL wp=(LL)(mo-a[0])*m%mo; FWT(a,0); a[wz]=wp; FWT(a,1); fo(i,0,m-1) printf("%d\n",a[i]); }

转载于:https://www.cnblogs.com/BAJimH/p/11013065.html