首页 > itarticle > km and m

km and m

admin 11月 14, 2020 0

题目链接

题意

计算 $sum_{k=1}^{N} ((kM) & M) mod 10^9+7$ .

思路

考虑所有与结果都是$M$有的二进制位，那我们不妨分别计算这些位的贡献。
$x$的第$i$位可以表示成 $left lfloor frac{x}{2^i} right rfloor - 2 times left lfloor frac{x}{2^{i+1} } right rfloor$ .

$ans = sum_{i=1}^{2^i leq M} sum_{k=1}^{N} left lfloor frac{x}{2^i} right rfloor - 2 times left lfloor frac{x}{2^{i+1} } right rfloor$ .
这两个东西都可以用类欧几里得算法在 $log$ 时间内计算。


using namespace std;
using LL = long long;

const int mod = 1e9 + 7, inv2 = (mod + 1) / 2;

LL n, m, ans;

LL (LL a, LL b, LL c, LL n) {
    if(!a) return 0;
    if(a >= c || b >= c) {
        LL tmp = calc(a % c, b % c, c, n);
        return (tmp + ((n % mod) * ((n + 1) % mod) % mod * inv2 % mod) * ((a / c) % mod) % mod + ((n + 1) % mod) * ((b / c) % mod) % mod) % mod;
    }
    LL f = ((__int128)a * n + b) / c;
    return (((n % mod) * (f % mod) % mod - calc(c, c - b - 1, a, f - 1)) % mod + mod) % mod;
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < 40; ++i) if(m >> i & 1) {
        LL res = ((calc(m, 0, 1LL << i, n) - 2 * calc(m, 0, 2LL << i, n)) % mod + mod) % mod;
        ans = (ans + (1LL << i) % mod * res % mod) % mod;
    }
    printf("%lldn", ans);
    return 0;
}