题面

题目描述

求：$\sum\limits_{i = 0}^{N}\sum\limits_{j = 0}^{M}i\or j$ ，其中 $\or$ 表示按位或运算。

思路

因为或是按位操作，不难想到计算每个二进制位的贡献，那么可以记：

  1. $n1[i]$ 为在 $0 -n$ 中第 $i$ 位为 $1$ 的有多少个。
  2. $m1[i]$ 为在 $0-m$ 中第 $i$ 位为 $1$ 的有多少个.

结果即为 $n1[i]\times m+m1[i]\times n-n1[i]\times m1[i]$ 。

代码

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

typedef long long ll;

const int P = 1e9 + 7;

ll n, m;

void Input() {
    scanf("%lld%lld", &n, &m);
}

ll count(ll n, int k) {
    ll L = 1LL << (k + 1);
    ll M = 1LL << k;
    ll ans = n / L * M;
    if(n % L > M) ans += n % L - M;
    return ans;
}

void Work() {
    n++, m++;
    ll ans = 0;
    for(int i = 0; i < 63; i++) {
        ll p1 = count(n, i), p0 = n - p1;
        ll q1 = count(m, i), q0 = m - q1;
        p1 %= P, p0 %= P, q1 %= P, q0 %= P;
        ans += ((p1 * q1 % P + p1 * q0 % P + p0 * q1 % P) % P * ((1LL << i) % P)) % P;
    }
    printf("%lld", ans % P);
}

int main() {
    Input();
    Work();
    return 0;
}