题意
对于一个有两个参数的函数(f(l,r))
我们定义其值为：
在树状数组中(l-1)位置减一，(r)位置加一
最后得到的树状数组中不为(0)的位置的个数
求
(N leq 10^{18})
答案对(10^9+7)取模
解法
这题很巧妙
为了方便，我们把(f(l,r))重定义为在(l)处减一，(r)处加一
我们可以发现(f(l,r))其实就是(l)与(r)的二进制表示中所有的一的个数减去两倍其(lcp)中一的个数
这个还是很好发现的，参见(lowbit)的定义
由于(N)达到了(10^{18})考虑按位进行统计
从高位到低位枚举(lcp)，设当前枚举到(i)，(n)在二进制表示下的长度为(len)
则(i...len)为当前串的(lcp)
则这种情况下(lcp)的贡献为(lcp)中一的个数
如果第(i-1)位为(1)，那么为了使(lcp)保持在(i...len)，第(i-1)为一定只能填(0)
由于这一位填(0)，我们保证了填的数一定小于上界
这样(i)之后的数一定可以贴上界；当然也可以不贴上界
如果第(i-1)位为(0)，同理我们只能填(1)
这样我们没法保证填的数一定小于上界，所以(i)之后的数不能贴上界
考虑(lcp)贴上界与不贴上界时的贡献分别如何
当贴上界时：
现在我们已经确定了(i-1...n)的所有数
由于是贴上界的，我们应该保证在填完(1...i-2)之后所有数仍小于等于上界
所以填(1)的数有((1+pre[i-2]))种填法
这里的(pre)数组意义是将(n)二进制表示的每一个前缀单独提出来构成的数
填(0)的数已经保证了小于上界
于是有(2^{i-2})种填法
如果不贴上界：
(i-1...n)未确定，但一定小于上界
所以之前的数一共有(2^{i-2} imes 2^{i-2})种填法
而(lcp)的贡献则是(1...suf[i])中所有数(1)的个数，这个可以(O(logN))算出来
(suf[i])的定义与(pre[i])类似
最后按照之前提到的计算方法计算(f(l,r))即可
代码
#include <cstdio>
using namespace std;
const int N = 70;
const int mod = 1e9 + 7;
#define int long long
int T;
int bit[N];
long long n;
long long pow[N], pre[N];
inline long long max(long long x, long long y) {
return x > y ? x : y;
}
long long calc(long long r) {
r += 1;
int res = 0;
for (int i = 0; i <= 61; ++i) {
if (pow[i] > r) break;
long long x = r / pow[i + 1], y = r % pow[i + 1];
res = (res + 1LL * x * pow[i] % mod + max(y - pow[i], 0)) % mod;
}
return res;
}
signed main() {
scanf("%lld", &T);
pow[0] = 1;
for (int i = 1; i <= 61; ++i) pow[i] = (pow[i - 1] << 1) % mod;
while (T--) {
scanf("%lld", &n);
int len = 0, cnt = 0;
long long tmp = n, suf = 0, ans = 0;
while (tmp) bit[++len] = tmp & 1, tmp >>= 1;
for (int i = 1; i <= len; ++i) {
pre[i] = pre[i - 1];
if (bit[i]) pre[i] = (pre[i] + pow[i - 1]) % mod;
}
for (int i = len; i >= 1; --i) {
cnt += bit[i], suf = suf << 1 | bit[i];
if (bit[i - 1]) ans = (ans + 1LL * cnt * (pre[i - 2] + 1) % mod * pow[i - 2] % mod) % mod;
ans = (ans + 1LL * calc(suf - 1) % mod * pow[i - 2] % mod * pow[i - 2] % mod) % mod;
}
ans = (1LL * n % mod * calc(n) % mod - 2LL * ans % mod + mod) % mod;
printf("%lld
", ans);
}
return 0;
}