期望异或 / T3 / 大新闻
题目链接：luogu P3898
题目大意
有一个数，等概率选 0~n-1 里面的整数。
然后又 p 的概率可以知道这个数，然后选择 0~n-1 中一个异或它最大的数。
否则就是等概率选 0~n-1 里面的整数。
问你这两个数的异或值的期望值是什么。
思路
不难看出 p roll 出的两种情况我们可以分别讨论，然后再按概率乘起来加起来。
那首先不知道：
考虑枚举每一位看贡献的值：
那我们设 (f_i) 为 (f_i) 为 (1) 的概率，那就有 (2^{i+1}f_i(1-f_i))。
接着考虑如何求 (f_i)。
我们不难想到可以把位数相同且不会超过 (n) 一起讨论。
(0sim 2^{k-1}-1) 的这一位都是 (0)，(2^{k-1}sim2^{k}-1) 都是 (1)。
然后 (x2^k+2^{k-1}sim (x+1)2^k) 都是 (1)。
那不难想到整段的就是 (leftlfloordfrac{n}{2^{k+1}}
ight
floor2^k)，剩下一段可能有，可能没有。
有的话就是 (nmod 2^{k+1}-2^k)，没有的话这个值会小于 (0)，那就直接 (max{nmod 2^{k+1}-2^k,0})。
总的来说，就是：
(f_k=dfrac{leftlfloordfrac{n}{2^{k+1}}
ight
floor2^k+max{nmod 2^{k+1}-2^k,0}}{n})
接着考虑求知道的。（这题最阴间的部分）
也是同样的，考虑看每一位是否有 (1)。（而且我们要看的是 (0sim n-1)，就直接把 (n) 减一）
如果是 (1)，那也是就说，它可以选 (0)，后面的就可以任意选，那后面一定可以匹配出 (1)。
那就直接是贡献乘个数，直接就是 (2^k(n+1))。
如果是 (0)，那你要是 (1) 才可以，就要前面没有搞满，你考虑统计有多少个搞满的，然后减去就是没有搞满的。（最后还要减去当前位选 (0) 的）
那你搞完这里之后，这里就是一个搞满的，那就要统计搞满的就要加上 (2^k)。
接着再回来看 (1) 的时候统计搞满的要怎么变。
那你这个时候你可以选 (1) 也可以选 (0)，一种是搞满的一种是搞不满的。
那就是一半一半的概率，那原来可以搞满的就有一半不能搞满，就要除二。
然后就可以了。
代码
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
ll n, nn;
long double p, eps = 1e-7;
long double ans, an0, an1;
long double pp[71];
int b;
void work0() {
for (int i = 0; i < nn; i++) {
pp[i] = 1.0 * (n / (1ll << (i + 1))) * (1ll << i);//前面那些整段的
pp[i] += 1.0 * max(n % (1ll << (i + 1)) - (1ll << i), 0ll);//最后一段，注意可能会没有
pp[i] = pp[i] / (1.0 * n);
}
for (int i = 0; i < nn; i++) {
an0 = an0 + 1.0 * (1ll << (i + 1)) * pp[i] * (1.0 - pp[i]);//有的概率乘没有的概率乘贡献
}
}
void work1() {
n--; nn = 0;
ll tmp = n;
while (tmp) {
tmp >>= 1; nn++;
}
ll num1 = 0;//记录有多少个数不能在前面搞出 1
for (int i = nn - 1; i >= 0; i--) {
if ((n >> i) & 1) {
an1 = an1 + 1.0 * (1ll << i) * (n + 1ll);
num1 >>= 1;
}
else {
an1 = an1 + 1.0 * (1ll << i) * (n + 1ll - (1ll << i) - (num1 >> 1));
num1 += (1ll << i);
}
}
n++; nn = 0;
tmp = n;
while (tmp) {
tmp >>= 1; nn++;
}
an1 = an1 / (1.0 * n);
}
int main() {
scanf("%lld %LF", &n, &p);
ll tmp = n;
while (tmp) {
tmp >>= 1; nn++;
}
work0();
work1();
ans = an0 * (1.0 - p) + an1 * p;
//如果是 jzoj 就是注释掉的这一段
// while (ans - 10.0 >= eps) {
// b++;
// ans = ans / 10.0;
// }
// while (ans > eps && ans < 1) {
// b--;
// ans = ans * 10.0;
// }
//
// printf("%.8LF %d", ans, b);
printf("%.8LF", ans);
return 0;
}