经典的数位DP题目?

题目

3652: 大新闻

Description

# Input

Output

\(1<=N<=10^18\)

解题报告

显然是一道数位dp的题目,观察数据范围可知. 加密和不加密是完全没有关系的两个问题。 1. 加密:等概率的选取两个数异或的期望?\(ans_{1*n^2}=\sum_{i=1}^{W}f_i*(n-f_i)*2*(1<<i-1)\)非常显然,就是观察每个数位可以做出的贡献。 2. 未加密:对于\(x∈[0,n)\),寻找\(y\)使得\(x^y \to max\),将二进制推广成树状,那么显然最有的策略是对称的走,这样可以让每个数位都做出贡献,而如果不可以对称,就退而求其次好了.

对数位dp问题,我一向是很虚的,学长安利了一种具有普遍性的方法->疯狂枚举状态法,就是设计\(f[i][0/1][0/1][][][]\)这个姿势的式子,\(i\)表示枚举到的数位,后面的每个括号都是消除后效性的状态,然后枚举出所有的状态,显然有稳定的复杂度。

回到大新闻,f[i][1/0][1/0]表示从高开始到第\(i\)位,\(x\)是否卡边界,\(y\)是否卡边界的概率(存收益,期望都没问题)。然后就是很短(?)的代码了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
const int N=70;
typedef long long ll;
ll n,mi[N],have[N];
double f[N][2][2],g[N][2][2],p;
int a[N],w;
double one(){
int i,j,k,aa,bb,jj,kk;
double ans=0;
g[a[0]+1][1][1]=1.0/(double)n;
for (i=a[0];i;i--)
for (j=0;j<=1;j++)
for (k=0;k<=1;k++)
if (g[i+1][j][k]>0.0)
for (aa=0;aa<=1;aa++){
if (j)
if (aa<a[i])
jj=0;
else
if (aa==a[i])
jj=1;
else
continue;
else
jj=0;
if (k){
bb=aa^1;
if (bb>a[i]) bb^=1;
if (bb<a[i])
kk=0;
else
kk=1;
}else
bb=aa^1,kk=0;
f[i][jj][kk]+=f[i+1][j][k]+(double)mi[i-1]*g[i+1][j][k]*(double)(aa^bb);
g[i][jj][kk]+=g[i+1][j][k];
}
for (i=0;i<=1;i++)
for (j=0;j<=1;j++)
ans+=f[1][i][j];
return ans;
}
double two(){
ll x=n;a[0]=0;
double ans=0;
while(n){
a[++a[0]]=(int)(n%2);
n/=2;
}
int i,j;
for (n=x,i=a[0];i;i--){
if (a[i]){
n-=mi[i-1],have[i]+=n;
for (j=i-1;j;j--)
have[j]+=(i-2>=0?mi[i-2]:0LL);
}
}
for (n=x,i=a[0];i;--i)
ans+=(double)have[i]/(double)n*(double)(n-have[i])/(double)n*2.0*(double)mi[i-1];
return ans;
}
int main(){
// freopen("bignews.in","r",stdin);
// freopen("bignews.out","w",stdout);
scanf("%lld",&n);
scanf("%lf",&p);
ll x=n-1;
while (x){
a[++a[0]]=(int)(x%2);
x/=2;
}
mi[0]=1LL;
for (int i=1;i<=a[0];i++)
mi[i]=mi[i-1]*2LL;
printf("%lf\n",one()*p+two()*(1.0-p));
return 0;
}

留言