牛客2020寒假训练营3-E

牛客2020寒假训练营3-E

七月 15, 2020

E.牛牛的随机数

题意

现在牛牛从自然数区间[l1,r1]中随机给出一个数字a，牛可乐从自然数区间[l2,r2]中随机给出一个数字b。l,r<1e18问你a ⊕ b的数学期望。其中⊕为位运算符，表示按位取异或。

题解

将每一个数拆分成二进制和=1+2+4+8…
那么 a 异或 b的数学期望= (异或得到1 2 4 8 ..等二进制数产生的贡献)/总数

把所有的数字从0开始枚举，然后转化成二进制输出，我们发现二进制下最低位位的规律是010101…循环，倒数第二位是001100110011…循环，而倒数第三位是0000111100001111…循环。
接下来的话就跟上面差不多。
假设x∈[l1,R1]中二进制的最低位产生0的数目为cntx0二进制的最低位位产生1的数目为cntx1 y∈[l2,R2]中二进制的最低位位产生0的数目为cnty0二进制的最低位位产生1的数目为cnty1那么就产生了cnty0×cntx1+cntx0×cnty1的贡献。
如果是二进制的倒数第二位呢，那么就是(cnty0×cntx1+cntx0×cnty1)×2。

那么二进制的倒数第k位的贡献就为(cnty0×cntx1+cntx0×cnty1)×2^k

可以学习计算1到r某位二进制数上1的个数

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
# include<bits/stdc++.h>

using namespace std;
typedef long long ll;

# define endl '\n'

const ll mod=(ll)1e9+7;
ll qpow(ll x, ll y){
    ll ans=1;
    while(y){
        if(y&1)ans=ans*x%mod;
        y>>=1;x=x*x%mod;
    }
    return ans;
}
inline ll getcnt1(ll pos,int bits){
    pos++;///从0到pos共有pos+1个数
    ll ans=(pos/(2ll<<bits)*(1ll<<bits))%mod;///计算从1到pos有多少个1 对于bits位每隔(2<<bits)就有(1<<bits)个1和0
    ans=(ans+(pos/(1ll<<bits)&1)*(pos%(1ll<<bits)))%mod;///每隔奇数个(1<<bits)就会有连续的1 pos%(1ll<<bits)计算超过这部分的1
    return ans;
}
inline ll get1(ll L,ll R,int bits){return (mod+getcnt1(R,bits)-getcnt1(L-1,bits))%mod;}
inline ll get0(ll L,ll R,int bits){return (mod+(R-L+1)%mod-get1(L,R,bits))%mod;}

int main(){
    int t;cin>>t;
    while(t--){
        ll l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        ll invQ=(((r1-l1+1)%mod)*((r2-l2+1)%mod))%mod;
        invQ=qpow(invQ,mod-2);ll ans=0;
        for(int i=0;i<=62;i++){
            ll val=(1ll<<i)%mod;
            ans=(ans+((((get1(l1,r1,i)*get0(l2,r2,i)%mod+get1(l2,r2,i)*get0(l1,r1,i)%mod)*val)%mod)*invQ)%mod)%mod;
        }
        cout<<ans<<endl;
    }
}