P9223 「PEOI RD1」异或（XOR）题解
题意简述
给定两个正整数 n,mn, mn,m，求以下式子的值：
∑i=1n∑j=1m(i⊕j)(mod998244353)\sum_{i=1}^{n} \sum_{j=1}^{m} (i \oplus j) \pmod{998244353} i=1∑n j=1∑m (i⊕j)(mod998244353)
其中 ⊕\oplus⊕ 表示按位异或运算。
数据范围：1≤n,m≤10161 \le n, m \le 10^{16}1≤n,m≤1016。
题目分析
由于 nnn and mmm 高达 101610^{16}1016，直接双重循环枚举 iii and jjj 的时间复杂度为 O(nm)O(nm)O(nm)，显然会超时。我们需要利用异或运算的性质，将问题分解为二进制每一位独立计算。
按位贡献法
异或运算是按位独立的。对于任意整数 xxx，其二进制表示为 ∑k=0∞bk2k\sum_{k=0}^{\infty} b_k 2^k∑k=0∞ bk 2k，其中 bk∈{0,1}b_k \in \{0, 1\}bk ∈{0,1}。
因此，i⊕ji \oplus ji⊕j 的值可以表示为：
i⊕j=∑k=0∞((ik⊕jk)⋅2k)i \oplus j = \sum_{k=0}^{\infty} ((i_k \oplus j_k) \cdot 2^k) i⊕j=k=0∑∞ ((ik ⊕jk )⋅2k)
其中 iki_kik 和 jkj_kjk 分别表示 iii and jjj 在二进制第 kkk 位上的值（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} Ans =i=1∑n j=1∑m k=0∑∞ ((ik
⊕jk )⋅2k)=k=0∑∞ 2k(i=1∑n j=1∑m (ik ⊕jk ))
这意味着，我们可以单独计算每一位 kkk 对最终答案的贡献。第 kkk 位的贡献为 2k×Ck2^k \times C_k2k×Ck ，其中 CkC_kCk 是所有数对 (i,j)(i, j)(i,j) 中，满足 ik≠jki_k \neq j_kik =jk 的对数。
注意：
1. 中间做乘法时，乘积最高可达103210^{32}1032 ,long long 是不够用的,可以选择高精度或者用 __int128 进行中间乘法运算的载体
2. 一定要记得取模哦
AC代码
