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 B(a) 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;for(int i=1;i<N;i++) pw[i]=pw[i-1]*2;
    g[63][1][1]=1;
    for(int i=62;~i;i--) {
        int a=(n>>i)&1;
        for(int xx=0;xx<2;xx++) for(int yy=0;yy<2;yy++) {
            int zz=xx^yy;
            for(int aa=0;aa<2;aa++) for(int bb=0;bb<2;bb++) {
                if(aa && xx>a) continue;
                if(bb && 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;
     
    memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
     
    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];
    for(int i=l-1;i>=0;i--) {
        int a=(n>>i)&1,b=(n>>i)&1;
        for(int xx=0;xx<2;xx++) {
            for(int aa=0;aa<2;aa++) for(int bb=0;bb<2;bb++) if(g[i+1][aa][bb]) {
                if(aa && xx>a) continue;
                int yy=xx^1;
                if(bb && yy>b) yy^=1;
                int zz=xx^yy;
                int na=aa?xx==a:0,nb=bb?yy==b:0;
                double gg=0;
                if(aa) {
                    if(a) {
                        if(na) 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 {
                        if(na) 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;
                }
//              B(i),B(aa),B(bb),B(xx),B(yy),B(na),B(nb)<<endl;
//              B(zz),B(gg)<<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;
}