CF1151C

· · 题解

思路：

先考虑连续偶数的和：

\sum_{i=1}^{n} 2i \\ =2\sum_{i=1}^{n}i \\ =2\frac{n(n+1)}{2}\\ =n(n+1) \end{matrix} $。 然后是奇数的和： $\begin{matrix} \sum_{i=0}^{n} 2i+1 \\ =(2\sum_{i=0}^{n-1}i)+n \\ =2\frac{n(n-1)}{2}+n\\ =n(n-1)+n\\ =n^2 \end{matrix}

于是可以求出进行 k 轮的和。

那么对于一个 n 求第 1,2 \dots n 所有数的和可以考虑先求出最大的 k 使得 2^k-1 \le n。

那么对于进行了 k 轮后没算的数字可以考虑 k 的奇偶，然后算出要添加的种类的数的总个数，用总个数的贡献减去已有的贡献即可。

然后对于 [l,r] 这段区间可以拆分成 [1,r] - [1,l-1]，然后按照上面说的做即可。

由于中途怕爆 long long，所以用了 __int128。

Code：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

ll l, r;
array<ll, 3> s[70];

ll power(ll a, ll b) {
    ll res = 1;

    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1) res = res * a % mod;

    return res;
}

ll solve(ll n) {
    if (!n) return 0;

    ll k = 1;
    while ((1ll << (k + 1)) - 1 <= n)
        ++k;

    // cout << n << ' ' << k << endl;
    ll ans = s[k][0];
    if (k & 1) {
        ll even = s[k][2], cnt = n - s[k][1];
        ans = (__int128)ans + (__int128)cnt * (cnt + 1) % mod - (__int128)even * (even + 1) % mod;
        ans = (ans + mod) % mod;
    } else {
        ll odd = s[k][1], cnt = n - s[k][2];
        // cout << odd << ' ' << cnt <<  ' ' << n << endl;
        ans = ((__int128)ans + (__int128)cnt * (cnt - 1) % mod - (__int128)odd * (odd - 1) % mod + cnt - odd) % mod;
        ans = (ans + mod) % mod;
    }

    return ans;
}

int main() {
    ll odd = 0, even = 0;
    for (ll i = 1; i <= 60; ++i) {
        if (i & 1) odd += (1ll << (i - 1ll));
        else even += (1ll << (i - 1ll));

        s[i] = {((__int128)even * ((__int128)even + 1) % mod + (__int128)odd * ((__int128)odd - 1) % mod + (__int128)odd % mod) % mod, odd, even};
//      cout << s[i][0] << ' ' << i << endl;
    }

    scanf("%lld%lld", &l, &r);

    // cout << solve(r) << ' ' << solve(l - 1) << endl;

    printf("%lld\n", (solve(r) - solve(l - 1) + mod) % mod);

    return 0;
}