巅峰赛#24 T2 题解 100% AC

题目讲解

题目要求：
我们需要计算在区间 $[0, n]$ 内有多少个不同的数对 $(x, y)$（其中 $0 ≤ x < y ≤ n$），使得 $x$ 和 $y$ 的汉明距离（即二进制表示中不同位的数量）小于等于 $k$。由于结果可能很大，我们需要对 $998244353$ 取模。

汉明距离的定义：
两个整数 $x$ 和 $y$ 的汉明距离是它们的二进制表示中不同位的数量。可以通过异或运算 x ^ y 得到一个数，其中为 $1$ 的位表示 $x$ 和 $y$ 在该位上不同。然后统计这个异或结果中 $1$ 的个数即可。

输入格式：

• 第一行是一个整数 $t$，表示测试用例的数量。
• 每个测试用例包含两个整数 $n$ 和 $k$。

输出格式：

• 对于每个测试用例，输出满足条件的数对数量，对 $998244353$ 取模。

示例分析：

• 示例1：
  • 输入：

    5
    10 3
    11 3
    20 1
    20 2
    20 3
    

  • 输出：

    52
    62
    42
    114
    177
    

  • 解释：
    • 对于 $n = 10$ 和 $k = 3$，需要统计所有 $0 ≤ x < y ≤ 10$ 的数对中汉明距离 $≤ 3$ 的数量。
    • 类似地处理其他测试用例。

代码讲解

#include <bits/stdc++.h>
using namespace std;

// 计算两个数的汉明距离
int hd(int x, int y) {
    int res = x ^ y;  // 异或运算，得到不同位的标记
    int dis = 0;
    while (res > 0) {
        dis += res & 1;  // 统计最低位是否为1
        res >>= 1;       // 右移一位
    }
    return dis;
}

int main() {
    int t;
    cin >> t;  // 读取测试用例的数量
    while (t--) {
        int n, k;
        cin >> n >> k;  // 读取n和k
        int cnt = 0;    // 初始化计数器

        // 遍历所有可能的数对(x, y)，其中0 ≤ x < y ≤ n
        for (int i = 0; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (hd(i, j) <= k) {  // 如果汉明距离≤k
                    cnt = (cnt + 1) % 998244353;  // 计数并取模
                }
            }
        }

        cout << cnt << endl;  // 输出结果
    }
    return 0;
}

代码注释

1. 头文件和命名空间：

   #include <bits/stdc++.h>
   using namespace std;
   

   • #include <bits/stdc++.h> 是万能头文件，包含所有标准库。
   • using namespace std 允许直接使用标准库名称（如 cin、cout）。

2. 汉明距离计算函数 hd：

   int hd(int x, int y) {
       int res = x ^ y;  // 异或运算，得到不同位的标记
       int dis = 0;
       while (res > 0) {
           dis += res & 1;  // 统计最低位是否为1
           res >>= 1;       // 右移一位
       }
       return dis;
   }
   

   • x ^ y：异或运算，结果中为 $1$ 的位表示 $x$ 和 $y$ 在该位上不同。
   • res & 1：检查最低位是否为 $1$。
   • res >>= 1：右移一位，相当于除以 $2$。
   • 返回 dis，即汉明距离。

3. 主函数 main：

   int main() {
       int t;
       cin >> t;  // 读取测试用例的数量
       while (t--) {
           int n, k;
           cin >> n >> k;  // 读取n和k
           int cnt = 0;    // 初始化计数器
   

   • 读取测试用例数量 $t$。
   • 对于每个测试用例，读取 $n$ 和 $k$，并初始化计数器 $cnt$。

4. 遍历所有数对：

   for (int i = 0; i <= n; i++) {
       for (int j = i + 1; j <= n; j++) {
           if (hd(i, j) <= k) {  // 如果汉明距离≤k
               cnt = (cnt + 1) % 998244353;  // 计数并取模
           }
       }
   }
   

   • 双层循环遍历所有 $0 ≤ x < y ≤ n$ 的数对 $(i, j)$。
   • 调用 $hd(i, j)$ 计算汉明距离，如果 $≤ k$，则计数器 $cnt$ 加 1 并取模。

5. 输出结果：

   cout << cnt << endl;  // 输出结果
   

   • 输出当前测试用例的结果。

6. 程序结束：

   return 0;
   

   • 返回 $0$，表示程序正常结束。

总结

• 算法思路：

  • 直接遍历所有可能的数对 $(x, y)$，计算它们的汉明距离，并统计满足条件的数对数量。
  • 汉明距离的计算通过异或和位操作实现。

• 时间复杂度：

  • 对于每个测试用例，需要遍历 $O(n^2)$个数对。
  • 由于 $n$ 最多是 500，$t$ 最多是 500，总时间复杂度是 $O(t \cdot n^2)$，在数据范围内是可接受的。

• 空间复杂度：

  • 只使用了常数个额外变量，空间复杂度为 $O(1)$。

• 优化思考：

  • 当前解法是暴力解法，适用于较小的 $n$（如 $n ≤ 500$）。
  • 如果 $n$ 很大（如 $10^5$ 或更大），需要更高效的算法（如数位动态规划或组合数学优化），但本题数据范围允许暴力解法。

这个解法直观且易于实现，适合入门级别的汉明距离问题。