題目鏈接：點擊查看

題目大意：有一個轉盤，每次轉動得到 $0～n?1$（$n$ 是 2 的冪）的概率分別給出。最開始你有一個數 $x=0$，每次轉動轉盤得到一個數 $y$，如果 $x\oplus y>x$，就令 $x=x\oplus y$，否則 $x$ 不變。求使 $x=n?1$，期望轉動轉盤的次數。

題目分析：

求期望，考慮倒著的概率 $dp$

設 $P[i]$ 為轉到 $i$ 的概率，設 $E[i]$ 代表當前數字為 $i$，到達 $n?1$ 的期望步數，顯然 $E[n?1]=0$，答案是 $E[0]$

設 $S[x]$ 代表轉動一次轉盤后 $x$ 發生變化的概率（即變大）的概率，不難得到 $$S[x]=\sum _{x\oplus y>x}P[y]$$

那么 $E$ 的方程分成兩個部分也不難寫出：$$E[x]=(E[x]+1)?(1?S[x])+\sum _{\stackrel{x<z}{x\oplus y=z}}(E[z]+1)?P[y]$$

發現左右兩側都有 $E[x]$，所以移一下項得到：
$$E[x]=\frac{(1?S[x])+\sum _{\stackrel{x<z}{x\oplus y=z}}(E[z]+1)?P[y]}{S[x]}$$

對于 $S[x]$，我們發現只需要找到 $y$ 在二進制下最高位的 $1$，判斷一下在 $x$ 在二進制下是否為 $0$ 就可以確定是否存在貢獻，這個可以 $O(nlogn)$ 預處理出來

對于 $\sum _{\stackrel{x<z}{x\oplus y=z}}(E[z]+1)?P[y]$，不難發現是異或卷積的形式，又因為期望 $dp$ 是倒著推的，所以后面的答案會對前面的答案具有貢獻，這個可以用 $cdq$ 分治套 $FWT$ 來解決

需要注意的是，在分治的過程中后面的答案會影響前面的答案，所以我們需要先遞歸右子區間，然后再遞歸左子區間

最后就是如何確定公式中 $y$ 的取值范圍呢，如果每次都是取 $0～n?1$ 的話肯定不行，通過分析不難發現，每次拆出來的左右區間形如：
$$[xxx0000]～[xxx0111]+[xxx1000]～[xxx1111]$$

我們上述式子中的 $x$ 需要在左區間中取，$z$ 需要在右區間中取，而 $y$ 只需要滿足 $y=x\oplus z$ 即可，將上面的兩段區間進行異或可以得到 $y\in [1000,1111]$，這個每次通過位運算求解即可，不難發現 $y$ 和 $z$ 的區間剛好是等階的

代碼：

// Problem: Gambling Monster // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/11257/D // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; const int mod=1e9+7; int n; LL P[N],S[N],invS[N],E[N],tmp[20],a[N],b[N]; LL q_pow(LL a,LL b) {LL ans=1;while(b) {if(b&1) {ans=ans*a%mod;}a=a*a%mod;b>>=1;}return ans; } LL inv(int x) {return q_pow(x,mod-2); } void FWTxor(LL *f,int x,int len) {for(int mid=1;(mid<<1)<=len;mid<<=1){int R=mid<<1;for(int i=0;i<len;i+=R)for(int j=0;j<mid;j++){f[i+j]=(f[i+j]+f[i+j+mid])%mod;f[i+j+mid]=(f[i+j]-f[i+j+mid]+mod-f[i+j+mid]+mod)%mod;f[i+j]=f[i+j]*x%mod;f[i+j+mid]=f[i+j+mid]*x%mod;}} } void solve(int l,int r) {if(l==r) {E[l]=(E[l]+(1-S[l]+mod)*invS[l])%mod;return;}int mid=(l+r)>>1,len=mid-l+1,p=l^(mid+1);solve(mid+1,r);for(int i=0;i<len;i++) {a[i]=(E[i+mid+1]+1)%mod;b[i]=P[i+p];}FWTxor(a,1,len),FWTxor(b,1,len);for(int i=0;i<len;i++) {a[i]=a[i]*b[i]%mod;}FWTxor(a,(mod+1)>>1,len);for(int i=l;i<=mid;i++) {E[i]=(E[i]+a[i-l]*inv(S[i]))%mod;}solve(l,mid); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--) {memset(tmp,0,sizeof(tmp));memset(S,0,sizeof(S));memset(E,0,sizeof(E));int sum=0;read(n);for(int i=0;i<n;i++) {read(P[i]);sum+=P[i];}sum=inv(sum);for(int i=0;i<n;i++) {P[i]=P[i]*sum%mod;}for(int i=0;i<n;i++) {for(int j=16;j>=0;j--) {if(i>>j&1) {tmp[j]=(tmp[j]+P[i])%mod;break;}}}for(int i=0;i<n;i++) {for(int j=0;j<=16;j++) {if(!(i>>j&1)) {S[i]=(S[i]+tmp[j])%mod;}}invS[i]=inv(S[i]);}solve(0,n-1);cout<<E[0]<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的2021牛客多校6 - Gambling Monster(分治FWT优化期望dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。