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;
	}
}