专栏文章

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

HHerobrine6265
P9223题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqz7vl3
此快照首次捕获于
2025/12/04 13:09
3 个月前
此快照最后确认于
2025/12/04 13:09
3 个月前
查看原文
题目传送门

思路

Step 1：暴力

没啥说的
时间复杂度 O(nm)\Omicron(nm)
期望得分：10pts

Step 2：观察分析

首先显然的是最后的结果只与 [1,n][1,n] 和 [1,m][1,m] 内每一个二进制位上出现 11 的次数有关
记 [1,m][1,m] 内二进制第 ii 位为 11 的次数为 cnt1i\text{cnt1}_i，[1,n][1,n] 内二进制第 ii 位为 11 的次数为 cnt2i,pos=⌊log⁡2max⁡(n,m)⌋\text{cnt2}_i,\text{pos}=\lfloor\log_2\max(n,m)\rfloor
对第 kk 位分析，则在累加过程中有 n−cnt2kn-\text{cnt2}_k 次原式中 jj 在第 kk 位没有发生反转，贡献了 cnt1k\text{cnt1}_k 个 11；有 cnt2k\text{cnt2}_k 次在第 kk 位发生了反转，贡献了 m−cnt1km-\text{cnt1}_k 个 11。
则第 kk 位在结果中带来的 11 的数量（忽略进位）为 cnt1k(n−cnt2k)+cnt2k(m−cnt1k)\text{cnt1}_k(n-\text{cnt2}_k)+\text{cnt2}_k(m-\text{cnt1}_k)
则最终答案为
∑i=0pos2i×(cnt1i(n−cnt2i)+cnt2i(m−cnt1i))\sum_{i=0}^{\text{pos}}2^i\times(\text{cnt1}_i(n-\text{cnt2}_i)+\text{cnt2}_i(m-\text{cnt1}_i))
计算上式的时间复杂度为 O(pos)\Omicron(\text{pos}) 次，是可接受的，因此我们考虑如何快速得出 cnt1i\text{cnt1}_i 和 cnt2i\text{cnt2}_i
显然的，若第 ii 位不是 mm 最高位，则 cnt1i=⌊m+12i⌋×2i−1\text{cnt1}_i=\lfloor\frac{m+1}{2^i}\rfloor\times 2^{i-1}
若第 ii 位是 mm 最高位，则 cnt1i=max⁡(0,(m+1)mod  2j+1−2j)\text{cnt1}_i=\max(0,(m+1)\mod2^{j+1}-2^j)，原因在于从 00 开始计起则则 [0,2i−1)[0,2^{i-1}) 的第 ii 位为 00，[2i−1,2i)[2^{i-1},2^i) 的第 ii 位为 11
对 nn 同理，因此可以在 O(pos)\Omicron(\text{pos}) 内得出 cnt1,cnt2\text{cnt1},\text{cnt2} 的值
综上总时间复杂度为 O(T×pos)\Omicron(T\times\text{pos})，可以通过本题

AC Code

温馨提示：记得及时取模
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...