傳送門

文章目錄

• 題意：
• 思路：

題意：

給你一個大輪盤，被分成了$n$個區域$0,1,2,..,n?1$，每個區域被轉到的概率是$\frac{a_i}{{\sum }_{j=0}^{n?1}{a}_j}$，轉到第$i$個區域的時候得分是$i$。現在你初始有$x=0$分，每次轉動輪盤假設得到了$y$分，那么如果$x\oplus y\le x$的話，當前得分不會變化，否則將$x=x\oplus y$，當得分達到$n?1$的時候立即停止，問你轉轉盤輪數的期望。
$2\le n\le 2^{16}$，且$n$為$2$的冪次。

思路：

以下我們約定：$a_i$代表得分為$i$的概率。
考慮期望$dp$，我們這里倒著來推，所以設$f[i]$表示當得分為$i$的時候還需要進行的輪數期望是多少，很容易就可以得到$n^2$的一個轉移方程：$$f_i=\sum _{j=0}^{n?1}[(i\oplus j)>i](f_{i\oplus j}+1)?a_j+\sum _{j=0}^{n?1}[(i\oplus j\le i)](f_i+1)?a_j$$
考慮到方程兩邊都有$f[i]$，我們進行移項：
$$f_i=\frac{{\sum }_{j=0}^{n?1}{a}_j+{\sum }_{j=0}^{n?1}[(i\oplus j)>i]f_{i\oplus j}?a_j}{1?{\sum }_{j=0}^{n?1}[(i\oplus j\le i)]a_j}$$
這個式子一眼看去只能$n^2$求，可以發現瓶頸就在${\sum }_{j=0}^{n?1}[(i\oplus j)>i]f_{i\oplus j}?a_j$這個式子上，我們將其化簡一下，設$x=i,y=j,z=x\oplus y$，$f(x)={\sum }_{x\oplus y=z,z>x}f(z)a(y)$，看到$f(x)$的式子很像異或卷積，所以為了更直觀，繼續化簡$f(x)={\sum }_{z\oplus y=x,z>x}f(z)a(y)$。
觀察可知，那么去掉$z>x$的條件的話，這個就是一個異或卷積的裸式子了，考慮到對于$i$只有$>i$的$f$能對其有貢獻，所以考慮$cdq$分治來計算這個式子，就可以去掉$z>x$這個條件了。在分治的過程中，只需要先遞歸計算右邊的值，讓后計算當前左區間的值，再遞歸左區間處理子問題即可。
但是問題還沒有解決，$a(y)$怎么確定呢？在卷的過程中我們需要保證所有$a$都需要符合條件才可，不然會卷出來其他不合法的答案。考慮當前區間分成的兩部分$[l,mid],[mid+1,r]$對應的二進制分別是$[xxx000,xxx011],[xxx100,xxx111]$，發現了什么？我們計算左區間的時候，他們的$a$是那些部分呢？顯然答案應該是$a$中下標在$[100,111]$的范圍內的數，可以發現左區間$[xxx000,xxx011]$異或上區間內任何一個數都會準確的落在右區間的某個位置，且只有這些數能落在右區間。所以卷的時候讓右區間的$f$和上面的$a$對應區間卷起來即可。
遞歸到$l=r$的時候直接計算答案即可。

// 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("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=100010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; int a[N],b[N],c; LL f[N],iv2,u[N],all;LL qmi(LL a,LL b) {LL ans=1; a%=mod; a+=mod; a%=mod;while(b) {if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod; }int x[N], y[N]; void FWT_xor(int *a,int opt,int N) {for(int i=1;i<N;i<<=1)for(int p=i<<1,j=0;j<N;j+=p)for(int k=0;k<i;++k){int X=a[j+k],Y=a[i+j+k];a[j+k]=(X+Y)%mod;a[i+j+k]=(X+mod-Y)%mod;if(opt==-1)a[j+k]=1ll*a[j+k]*iv2%mod,a[i+j+k]=1ll*a[i+j+k]*iv2%mod;} }void cdq(int d,int l,int r,LL sa) {if(l==r) {f[l]+=all%mod; f[l]%=mod;(f[l]*=qmi(1-(all-sa)%mod,mod-2))%=mod;return;} int len=1<<d; LL sum=0;cdq(d-1,l+len,r,sa);for(int i=0;i<len;i++) {x[i]=a[i+len]; sum+=x[i]; sum%=mod;y[i]=f[i+l+len];}FWT_xor(x,1,len); FWT_xor(y,1,len);for(int i=0;i<len;i++) {x[i]=1ll*x[i]*y[i]%mod;}FWT_xor(x,-1,len);for(int i=0;i<len;i++) {(f[i+l]+=x[i])%=mod; }cdq(d-1,l,l+len-1,(sa+sum)%mod); }int main() { // ios::sync_with_stdio(false); // cin.tie(0);iv2=qmi(2,mod-2);int _; scanf("%d",&_);while(_--) {scanf("%d",&n); LL sum=0;memset(f,0,sizeof(f));for(int i=0;i<n;i++) scanf("%d",&a[i]),sum+=a[i];sum=qmi(sum,mod-2); all=0;for(int i=0;i<n;i++) a[i]=a[i]*sum%mod,all+=a[i],all%=mod;for(int i=16;i>=0;i--) {if((1<<i)==n) {cdq(i-1,0,n-1,0);break;}}printf("%lld\n",f[0]%mod);}return 0; } /* 200000005 3 3 0*/ 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的2021牛客暑期多校训练营6 :D Gambling Monster 期望dp + fwt + cdq分治的全部內容，希望文章能夠幫你解決所遇到的問題。

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