BZOJ 3652: 大新闻(数位DP+概率论)

不得不说数位DP和博弈论根本不熟啊QAQ，首先这道题嘛~~~可以分成两个子问题：

1. 有加密：直接算出0~n中二进制每一位为0或为1分别有多少个，然后分位累加求和就行了= =

2. 无加密：分别算出0~n中二进制每一位为0或为1分别有多少个，然后对于为0或1该分别采取什么措施，对后面位数会有什么影响就行了

说白了就是这么简单（别打我QAQ）然后就是慢慢找到dp的正确方式了QAQ（请原谅我的蒟蒻，调了2天QAQ）

CODE：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

int len;long long n;

double a[100];

double part2(){

double ans=0;long long m=n;

a[0]=n&1?2.0/(n+1):1.0/(n+1);

for (int i=1;i<len-1;i++)

if (n&(1ll<<i)) a[i]=a[i-1]+(1ll<<i)*1.0/(n+1)*(1ll<<i)*2+((1ll<<i)-1)*1.0/(n+1)*(1ll<<i);

else a[i]=a[i-1]*2+(1ll<<i)*1.0/(n+1)*(1ll<<i);

for (int i=len-1;i>=0;i–){

if (n&(1ll<<i)) {

if (m&(1ll<<i)){

ans+=((1ll<<(i+1))-1)*1.0*(m+1-(1ll<<i))/(n+1);

m=(1ll<<i)-1;

}

ans+=(1ll<<i)*1.0*(m+1)/(n+1);

}else

if (m&(1ll<<i)){

ans+=(1ll<<i)*1.0*(m+1-(1ll<<i))/(n+1);

m^=(1ll<<i);

ans+=i-1>=0?a[i-1]:0;

}

}

return ans;

}

double part1(){

double ans=0;n++;

for (int i=len-1;i>=0;i–){

double pi=(n/(1ll<<(i+1))*1.0*(1ll<<i) + (max ((n % (1ll<<(i+1)))-(1ll<<i),0ll)*1.0))*1.0 /n;

ans+=pi*2*(1-pi)*(1ll<<i);

}

return ans;

}

int main(){

double p;

scanf("%lld%lf",&n,&p);

n–;

while ((1ll<<len)<=n) len++;

double ans2=part2();

double ans1=part1();

printf("%lf\n",ans1*(1-p)+ans2*(p));

return 0;

}