传送门

文章目录

• 题意：
• 思路：

题意：

给你一个大轮盘，被分成了$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)\ast a_j+\sum _{j=0}^{n-1}[(i\oplus j\le i)](f_i+1)\ast 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}\ast 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}\ast 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分治的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。