正題

題目鏈接:https://www.luogu.com.cn/problem/AT4996

---

題目大意

給出一個$0～2^n?1$下標(biāo)的數(shù)組$p$，$p_i$表示有$p_i$的權(quán)重概率選擇$i$。

開始有一個$x=0$，每次選擇一個數(shù)字$y$讓$x=xxory$

對于每個$i$求期望多久后第一次變成$i$。

$1\le n\le 18$

---

解題思路

搞一個異或卷積的生成函數(shù)，先搞出概率的函數(shù)$P$。

然后設(shè)$E$表示答案的函數(shù)，那么有
$$E\times P+I=E+c$$
$c$表示余項，$I(x)={\sum }_{i=1}^{\infty }{x}^i$

先求出余項$c$來，設(shè)$S(A)$表示生成函數(shù)$A$的所有系數(shù)和
$$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=0$，我們要把所有的答案減去$E_0$

時間復(fù)雜度$O(2^{n}n)$

---

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; }

總結(jié)

以上是生活随笔為你收集整理的AT4996-[AGC034F]RNG and XOR【FWT,生成函数】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。