BZOJ 3652: 大新闻

Description

有p)的概率没有被加密。求期望。

如果没有被加密那么求[0,n))随机选择一个数x)然后再选择小于n)的y)使x)^y)最大的异或和的期望。

如果被加密那么求随机选择[0,n))两个数x,y)，求异或和的期望。

Solution

数位DP.

强行期望？

被加密了那就很简单了，跟SDOI2016一样。

如果没被加密，我做的方法比较蠢…做法还是一样，状态表示也是一样…

分类讨论统计出来个数，然后统计答案，为了方便我算的是小于等于n)的…

Code

/**************************************************************
    Problem: 3652
    User: BeiYu
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1296 kb
****************************************************************/
 
#include <bits/stdc++.h>
using namespace std;
 
#define Ba) cout<<#a)<<"="<<a<<" "
 
typedef long long LL;
typedef long double LD;
const int N = 70;
 
LL n;
double p,ans,tmp;
double f[N][2][2];
double g[N][2][2];
double pw[N];
 
int main) {
    cin>>n>>p;
    pw[0]=1;forint i=1;i<N;i++) pw[i]=pw[i-1]*2;
    g[63][1][1]=1;
    forint i=62;~i;i--) {
        int a=n>>i)&1;
        forint xx=0;xx<2;xx++) forint yy=0;yy<2;yy++) {
            int zz=xx^yy;
            forint aa=0;aa<2;aa++) forint bb=0;bb<2;bb++) {
                ifaa && xx>a) continue;
                ifbb && yy>a) continue;
                int na=aa?xx==a):0,nb=bb?yy==a):0;
                f[i][na][nb]+=f[i+1][aa][bb]+zz*pw[i]*g[i+1][aa][bb];
                g[i][na][nb]+=g[i+1][aa][bb];
            }
        }
    }
    ans=1-p)*f[0][0][0]/n/n;
     
    memsetf,0,sizeoff)),memsetg,0,sizeofg));
     
    n--;
    int l=63;for;pw[l]>n;l--);
    g[l][0][1]=pw[l],g[l][1][0]=n-pw[l]+1;
    f[l][0][1]=pw[l]*g[l][0][1],f[l][1][0]=pw[l]*g[l][1][0];
    tmp+=f[l][0][1]+f[l][1][0];
    forint i=l-1;i>=0;i--) {
        int a=n>>i)&1,b=n>>i)&1;
        forint xx=0;xx<2;xx++) {
            forint aa=0;aa<2;aa++) forint bb=0;bb<2;bb++) ifg[i+1][aa][bb]) {
                ifaa && xx>a) continue;
                int yy=xx^1;
                ifbb && yy>b) yy^=1;
                int zz=xx^yy;
                int na=aa?xx==a:0,nb=bb?yy==b:0;
                double gg=0;
                ifaa) {
                    ifa) {
                        ifna) g[i][na][nb]+=g[i+1][aa][bb]-pw[i-1],gg=g[i+1][aa][bb]-pw[i-1];
                        else g[i][na][nb]+=pw[i-1],gg=pw[i-1];
                    } else {
                        ifna) g[i][na][nb]+=g[i+1][aa][bb],gg=g[i+1][aa][bb];
                    }
                } else {
                    g[i][na][nb]+=g[i+1][aa][bb]/2,gg=g[i+1][aa][bb]/2;
                }
//              Bi),Baa),Bbb),Bxx),Byy),Bna),Bnb)<<endl;
//              Bzz),Bgg)<<endl;
                f[i][na][nb]+=zz*pw[i]*gg;
                tmp+=zz*pw[i]*gg);
            }
        }
    }
    ans=ans+p*tmp/n+1));
    printf"%.11lf
",ans);
    return 0;
}