「PEOI Rd1」异或（xor）

userId_undefined
Suger_zhy🤔
题解仙人秩序白银

2026-09-18 21:26:20

发布于：湖北

41阅读
0回复
0点赞

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

题意简述

给定两个正整数 n,mn, m，求以下式子的值：

∑i=1n∑j=1m(i⊕j)(mod998244353)\sum_{i=1}^{n} \sum_{j=1}^{m} (i \oplus j) \pmod{998244353}

其中 ⊕\oplus 表示按位异或运算。

‌数据范围‌：1≤n,m≤10161 \le n, m \le 10^{16}。

题目分析

由于 nn and mm 高达 101610^{16}，直接双重循环枚举 ii and jj 的时间复杂度为 O(nm)O(nm)，显然会超时。我们需要利用异或运算的性质，将问题分解为二进制每一位独立计算。

按位贡献法

异或运算是按位独立的。对于任意整数 xx，其二进制表示为 ∑k=0∞bk2k\sum_{k=0}^{\infty} b_k 2^k，其中 bk∈{0,1}b_k \in \{0, 1\}。
因此，i⊕ji \oplus j 的值可以表示为：

i⊕j=∑k=0∞((ik⊕jk)⋅2k)i \oplus j = \sum_{k=0}^{\infty} ((i_k \oplus j_k) \cdot 2^k)

其中 iki_k 和 jkj_k 分别表示 ii and jj 在二进制第 kk 位上的值（0 或 1）。

我们将求和公式展开并交换求和顺序：

Ans=∑i=1n∑j=1m∑k=0∞((ik⊕jk)⋅2k)=∑k=0∞2k(∑i=1n∑j=1m(ik⊕jk))\begin{aligned} \text{Ans} &= \sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{k=0}^{\infty} ((i_k \oplus j_k) \cdot 2^k) \\ &= \sum_{k=0}^{\infty} 2^k \left( \sum_{i=1}^{n} \sum_{j=1}^{m} (i_k \oplus j_k) \right) \end{aligned}

这意味着，我们可以单独计算每一位 kk 对最终答案的贡献。第 kk 位的贡献为 2k×Ck2^k \times C_k，其中 CkC_k 是所有数对 (i,j)(i, j) 中，满足 ik≠jki_k \neq j_k 的对数。

注意：

  1. 中间做乘法时，乘积最高可达103210^{32} ,long long 是不够用的,可以选择高精度或者用 __int128 进行中间乘法运算的载体

  2. 一定要记得取模哦

AC代码

#include<iostream>
using namespace std;
using ll=long long;
using int1=__int128;
ll aaa(ll N,ll k) {
    if (N <= 0){
        return 0;
    }
    ll x1=1LL<<(k+1),x2 = 1LL<<k;
    ll x3=N/x1;
    ll cnt=x3 *x2;
    ll r=N%x1;
    if(r>=x2) {
        cnt+=r-x2+1;
    }
    return cnt;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a;
    cin>>a;
    while(a--) {
        long long n,m;
        cin >> n >> m;
        long long ans = 0;
        for (ll k=0;k<60;k++) {
            int1 a1=aaa(n,k);
            int1 b1=n-a1;
            int1 a2=aaa(m,k);
            int1 b2=m-a2;
            int1 p1=a1*b2;
            int1 p2=b1*a2;
            int1 t=p1+p2;
            int1 m=t % 998244353;
            ll p = (1LL << k) % 998244353; 
            int1 c=(m*p)%998244353;
            ans=(ans+c)%998244353;
        }
        cout << ans << endl;
    }
    return 0;
}
userId_undefined
去预览
0/2000

全部评论 6

热门讨论