题解：P9223 「PEOI Rd1」异或（xor）

Herobrine6265 · 2024-11-27 12:29:13 · 题解

题目传送门

思路

Step 1：暴力

没啥说的

时间复杂度 \Omicron(nm)

期望得分：10pts

Step 2：观察分析

首先显然的是最后的结果只与 [1,n] 和 [1,m] 内每一个二进制位上出现 1 的次数有关

记 [1,m] 内二进制第 i 位为 1 的次数为 \text{cnt1}_i，[1,n] 内二进制第 i 位为 1 的次数为 \text{cnt2}_i,\text{pos}=\lfloor\log_2\max(n,m)\rfloor

对第 k 位分析，则在累加过程中有 n-\text{cnt2}_k 次原式中 j 在第 k 位没有发生反转，贡献了 \text{cnt1}_k 个 1；有 \text{cnt2}_k 次在第 k 位发生了反转，贡献了 m-\text{cnt1}_k 个 1。

则第 k 位在结果中带来的 1 的数量（忽略进位）为

则最终答案为

计算上式的时间复杂度为 \Omicron(\text{pos}) 次，是可接受的，因此我们考虑如何快速得出 \text{cnt1}_i 和 \text{cnt2}_i

显然的，若第 i 位不是 m 最高位，则 \text{cnt1}_i=\lfloor\frac{m+1}{2^i}\rfloor\times 2^{i-1}

若第 i 位是 m 最高位，则 \text{cnt1}_i=\max(0,(m+1)\mod2^{j+1}-2^j)，原因在于从 0 开始计起则则 [0,2^{i-1}) 的第 i 位为 0，[2^{i-1},2^i) 的第 i 位为 1

对 n 同理，因此可以在 \Omicron(\text{pos}) 内得出 \text{cnt1},\text{cnt2} 的值

综上总时间复杂度为 \Omicron(T\times\text{pos})，可以通过本题

AC Code

温馨提示：记得及时取模

#include <iostream>
#define ll long long

using namespace std;

const int mod = 998244353;

ll pow2[60] = {1};

signed main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    for (int i = 1; i < 60; i++)
        pow2[i] = (pow2[i - 1] << 1);
    while (t--)
    {
        ll n, m, ans = 0;
        cin >> n >> m;
        for (int j = 0, cnt1, cnt2; pow2[j] <= max(m, n); j++)
        {
            cnt1 = (m + 1) / pow2[j + 1] % mod * pow2[j] % mod + max(0ll, (m + 1) % pow2[j + 1] - pow2[j]) % mod;
            cnt1 %= mod;
            cnt2 = (n + 1) / pow2[j + 1] % mod * pow2[j] % mod + max(0ll, (n + 1) % pow2[j + 1] - pow2[j]) % mod;
            cnt2 %= mod;
            ans += (m - cnt1) % mod * (pow2[j] % mod) % mod * cnt2 % mod;
            ans %= mod;
            ans += (n - cnt2) % mod * (pow2[j] % mod) % mod * cnt1 % mod;
            ans %= mod;
        }
        cout << ans << '\n';
    }
    return 0;
}