E 牛牛的随机数
链接：https://ac.nowcoder.com/acm/contest/3004/E
来源：牛客网
题目描述
牛牛和牛可乐是一对好朋友，现在牛牛从值域[l1,r1]中随机给出一个数字a，牛可乐从值域[l2,r2]中随机给出一个数字b。问你a⊕ b的数学期望。其中⊕为位运算符，表示按位取异或。
为了避免你输出的答案出现精度误差，请你输出一个分数P∗Q−1(mod 109+7)P*Q^{-1}(mod\,\, 10^9+7)P∗Q−1(mod109+7) ，其中Q−1Q^{-1}Q−1表示在mod 条件下的乘法逆元。数据保证gcd(Q,109+7)=1gcd(Q,10^9+7)=1gcd(Q,109+7)=1，也就是说保证Q−1Q^{-1}Q−1在该模条件下有意义。
输入描述:
第一行是一个正整数T(1≤T≤1e5)表示有T组案例。
接下来T行，每行四个正整数l1,r1,l2,r2（1≤l1≤r1≤1e18,1≤l2≤r2≤1e18）。
输出描述:
请输出期望P∗Q−1(mod 109+7)
输入
2
3 5 7 8
1 3 3 5 输出
500000011
222222228 说明
a可取3,4,5，b可取7,8
3⊕7=4，4⊕7=3，5⊕7=2
3⊕8=11，4⊕8=12，5⊕8=13
思路：计算每一位的1和0分别的个数，计算每一位的贡献
代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
ll po[100];
ll quickpow(ll x, ll y, ll mod)
{
if (y == 0)return 1;
if (y == 1)return x % mod;
else
{
if (y % 2 == 0)
{
ll t = quickpow(x, y / 2, mod);
return t * t%mod;
}
else
{
ll t = quickpow(x, y / 2, mod);
t = t * t%mod;
return (t * (x%mod)) % mod;
}
}
}
ll g(ll x, ll n)//统计1-x第n位上1的个数和
{
ll xx = (ll)((x + 1) / po[n])*(ll)po[n-1];
//cout<<"xx "<<xx<<endl;
ll yy = (ll)(x + 1) % ((ll)po[n]) - (ll)po[n-1];
//cout<<"yy "<<yy<<endl;
if (yy >= 0)xx += yy;
return xx;
}
ll h1(ll l, ll r, ll n)//返回l~r第n位所有的1的个数和
{
return g(r, n) - g(l - 1, n);
}
int main()
{
po[0] = 1;
for (int i = 1; i <= 63; i++)po[i] = 2 * po[i - 1];
//cout << po[60] << " " << po[61] << " " << po[62] << endl;
int t;
cin >> t;
ll l1, r1, l2, r2;
while (t--)
{
cin >> l1 >> r1 >> l2 >> r2;
if (r1 - l1 + 1 % mod == 0 || r2 - l2 + 1 % mod == 0)
{
cout << 0 << endl;
continue;
}
ll res = 0;
for (ll i = 1; i <= 60; i++)
{
ll ans2 = quickpow(2, i - 1, mod);
//cout << h1(l1, r1, i) % mod << " " << (r2 - l2 + 1 - h1(l2, r2, i)) % mod << endl;
//cout << (ll)(h1(l1, r1, i) % mod)*(ll)((r2 - l2 + 1 - h1(l2, r2, i)) % mod) << endl;
ll ansa = ((ll)(h1(l1, r1, i) % mod )*(ll)( (r2 - l2 + 1 - h1(l2, r2, i)) % mod))%mod; // cout << "ansa " << ansa << endl;
ll ansb = ((ll)((r1 - l1 + 1 - h1(l1, r1, i)) % mod) *(ll)(h1(l2, r2, i)% mod)) % mod; // cout << "ansb " << ansb << endl;
ll ansc = (ansa + ansb) % mod; //cout << "ansc " << ansc << endl;
ll ansd = (ans2*ansc) % mod; // cout << "ansd " << ansd << endl;
res = ((ll)(res%mod)+(ll)(ansd)) % mod;
// cout <<"res "<< res << endl;
}
ll x1 = (r1 - l1 + 1) % mod;
ll x2 = (r2 - l2 + 1) % mod;
ll q = x1 * x2%mod;
q = quickpow(q, mod - 2, mod);
//cout << res << " " <<q<< endl;
cout << res * q%mod << endl;
}
}
查看13道真题和解析