牛客寒假算法训练营（第3期）

牛客寒假算法训练营3

这一次确实非常困难。。。。。

E牛牛的随机数

链接：https://ac.nowcoder.com/acm/contest/3004/E
来源：牛客网

牛牛与牛可乐是亲密无间的好友，当前牛牛从数值范围[l1,r1]中随机选取一个数值a，而牛可乐则从数值区间[l2,r2]中随机选取一个数值b。请计算a与b按位异或运算后的数学期望值。其中⊕代表按位异或运算。

为避免输出结果存在精度偏差，请以分数形式P∗Q−1(mod 109+7)进行输出，其中Q−1表示在模运算条件下的乘法逆元。数据确保gcd(Q,109+7)=1，即Q−1在该模数下具有明确的定义，并且(r1−l1+1)(r2−l2+1)不会成为模数的倍数。

最终的答案表达式为\frac{\sum_{x = l_1}^{r_1}\sum_{x = l_2}^{r_2}x\bigoplus y}{(r_1-l_1 + 1) * (r_2 - l_2 + 1)}

首先需要明确的是，对最终结果产生影响的是每一位的贡献情况。先分析第0位带来的贡献，该位的总贡献可以分为两部分：[l1,r1]区间内第0位为“1”的数字数量乘以[l2,r2]区间内第0位为“0”的数字数量，加上[l1,r1]区间内第0位为“0”的数字数量乘以[l2,r2]区间内第0位为“1”的数字数量。对于任意第k位而