CDMA - 题解

标签与难度

标签: 构造, 分治, 位运算, 数学, 矩阵, Hadamard 矩阵 难度: 1600

题目大意喵~

主人你好呀，这道题是关于构造一个特殊的矩阵哦，喵~

题目要求我们构建一个 $m \times m$ 的方阵，其中 $m$ 是2的正整数次幂。这个方阵里只能填 1 和 -1 这两种数字。最关键的要求是，任意抽取方阵中的两行（不同的两行哦！），它们必须是“正交”的。

“正交”听起来有点吓人，但其实就是指这两行的内积为0，呐。所谓内积，就是把这两行对应位置的数字相乘，然后再把这些乘积全部加起来。

举个栗子，假设有两行 s = [s1, s2, ..., sm] 和 t = [t1, t2, ..., tm]，它们的内积就是：

$$s \cdot t = \sum_{i=1}^{m} s_i \times t_i = 0$$

我们的任务就是找出这样一个神奇的 $m \times m$ 矩阵，然后把它打印出来。如果有很多种答案，随便打印一种就可以啦，喵~

解题思路分析

这道题看起来有点抽象，但别担心，跟着我的思路一步步来，很快就能找到线索的！

从最小的例子开始喵！

我们先不想那么大的 $m$，从最小的 $m$ 开始思考。因为 $m$ 是2的幂，所以最小的 $m$ 是 $2^1 = 2$。

我们需要一个 $2 \times 2$ 的矩阵，里面填满 1 和 -1。假设第一行是 [r11, r12]，第二行是 [r21, r22]。根据题意，它们的内积必须是 0。

$$r_{11} \times r_{21} + r_{12} \times r_{22} = 0$$

因为所有元素都是 1 或 -1，所以每个乘积项也只能是 1 或 -1。两个数相加等于0，那它们必须是 1 和 -1。

我们可以试着构造一下。比如说，让 r11 * r21 = 1，r12 * r22 = -1。

• r11 * r21 = 1 意味着 r11 和 r21 必须相同。我们都设为 1 吧。
• r12 * r22 = -1 意味着 r12 和 r22 必须相反。我们让 r12 = 1，r22 = -1 吧。

这样，第一行就是 [1, 1]，第二行就是 [1, -1]。我们得到了一个解：

$$H_2 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$

是不是很简单呀？喵~

怎么从小的构造出大的呢？

现在我们有了 $2 \times 2$ 的解，那 $4 \times 4$ 的怎么办呢？难道要再猜一次吗？那可太麻烦啦！我的爪子可不想做那么多重复劳动。

这里有一个非常巧妙的分治思想，可以从一个 $n \times n$ 的解（我们叫它 $H_n$）构造出一个 $2n \times 2n$ 的解（$H_{2n}$）。

想象一下，我们把 $H_{2n}$ 切成四块，每一块都是一个 $n \times n$ 的小矩阵：

$$H_{2n} = \begin{pmatrix} A & B \\ C & D \end{pmatrix}$$

其中 $A, B, C, D$ 都是 $n \times n$ 的矩阵。我们可以用我们已知的 $H_n$ 来填充它们！一个神奇的构造方法是这样的：

$$H_{2n} = \begin{pmatrix} H_n & H_n \\ H_n & -H_n \end{pmatrix}$$

这里的 $-H_n$ 就是把 $H_n$ 矩阵里的每个元素都取反（1 变 -1，-1 变 1）。

我们来验证一下这个构造为什么是正确的，呐。 令 $H_n$ 的第 $i$ 行是向量 $r_i$。 那么 $H_{2n}$ 的前 $n$ 行就是 $[r_i, r_i]$（把 $r_i$ 复制一遍拼起来），后 $n$ 行就是 $[r_i, -r_i]$（把 $r_i$ 和它的反向量拼起来）。

我们来检查任意两行 $u, v$ 的内积：

1. 如果 $u, v$ 都来自 $H_{2n}$ 的上半部分： $u = [r_i, r_i]$, $v = [r_j, r_j]$ (其中 $i \neq j$) $u \cdot v = (r_i \cdot r_j) + (r_i \cdot r_j) = 0 + 0 = 0$。 （因为 $H_n$ 本身满足条件，所以 $r_i \cdot r_j=0$）

2. 如果 $u, v$ 都来自 $H_{2n}$ 的下半部分： $u = [r_i, -r_i]$, $v = [r_j, -r_j]$ (其中 $i \neq j$) $u \cdot v = (r_i \cdot r_j) + ((-r_i) \cdot (-r_j)) = (r_i \cdot r_j) + (r_i \cdot r_j) = 0 + 0 = 0$。

3. 如果 $u$ 来自上半部分， $v$ 来自下半部分： $u = [r_i, r_i]$, $v = [r_j, -r_j]$$u \cdot v = (r_i \cdot r_j) + (r_i \cdot (-r_j)) = (r_i \cdot r_j) - (r_i \cdot r_j)$。

   • 如果 $i \neq j$，结果是 $0 - 0 = 0$。
   • 如果 $i = j$（即同一基础行的衍生），结果是 $(r_i \cdot r_i) - (r_i \cdot r_i) = 0$。 这里 $r_i \cdot r_i = \sum_{k=1}^n (r_{ik})^2$。因为 $r_{ik}$ 是 1 或 -1，所以 $(r_{ik})^2 = 1$。所以 $r_i \cdot r_i = n$。但无论如何，相减之后总是0！

太棒了！这个构造方法是完全正确的！我们可以从 $H_1 = \begin{pmatrix} 1 \end{pmatrix}$ 开始，不断用这个方法生成 $H_2, H_4, H_8, \dots$ 直到 $H_m$。这种矩阵在数学上被称为阿达马矩阵(Hadamard Matrix)。

一个更神奇的发现！

递归构造虽然很棒，但有没有更直接的方法呢？我用我敏锐的猫眼观察了一下生成的矩阵，发现了一个惊人的规律，这和位运算有关！

我们用0-based索引（行号和列号都从0到 $m-1$）来看看 $H_4$：

$$H_4 = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix}$$

我们来算一下 (行号 & 列号) 的二进制中 1 的个数（也就是 popcount）。

• H[0][0]: popcount(0&0) = popcount(0) = 0 (偶) -> 1
• H[1][1]: popcount(1&1) = popcount(1) = 1 (奇) -> -1
• H[2][3]: popcount(2&3) = popcount(0b10 & 0b11) = popcount(0b10) = 1 (奇) -> -1
• H[3][3]: popcount(3&3) = popcount(3) = popcount(0b11) = 2 (偶) -> 1

好像... H[i][j] 的值只取决于 popcount(i & j) 的奇偶性！

$$H_{ij} = (-1)^{\text{popcount}(i \ \& \ j)}$$

如果 popcount(i & j) 是偶数，值为 1；如果是奇数，值为 -1。

这简直是魔法，对吧！这个公式可以一步到位生成整个矩阵，不需要递归，非常高效！我们可以用这个公式来写代码，既简洁又快速，喵~

代码实现

下面就是用这个神奇的位运算公式写出的代码啦！我特地加了详细的注释，希望能帮到你，喵~

#include <iostream>
#include <vector>

// __builtin_popcount 是一个GCC/Clang内置函数，用来快速计算一个整数的二进制表示中有多少个'1'。
// 如果你的编译器不支持，可以自己手写一个，比如：
// int popcount(int x) {
//     int count = 0;
//     while (x > 0) {
//         x &= (x - 1); // 这个操作可以消除最右边的'1'
//         count++;
//     }
//     return count;
// }

int main() {
    // 为了更快的输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int m; // 矩阵的边长
    std::cin >> m;

    // 我们使用0-based索引，从 0 到 m-1，这样和位运算更搭哦
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            // 计算行号 i 和列号 j 的按位与 (bitwise AND)
            int bitwise_and_result = i & j;

            // 计算结果中'1'的个数
            int set_bits_count = __builtin_popcount(bitwise_and_result);

            // 根据'1'的个数的奇偶性来决定是 1 还是 -1
            // 偶数 -> 1, 奇数 -> -1
            if (set_bits_count % 2 == 0) {
                std::cout << 1;
            } else {
                std::cout << -1;
            }

            // 在同一行的数字之间打印空格，行末不打印
            if (j < m - 1) {
                std::cout << " ";
            }
        }
        // 每打印完一行，换行
        std::cout << "\n";
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O(m^2)$ 我们需要填充一个 $m \times m$ 的矩阵。对于矩阵中的每一个位置 $(i, j)$，我们都执行了一次位与运算和一次 popcount 运算。这些操作都可以看作是常数时间完成的。所以总的时间复杂度就是 $O(m^2)$，正好是输出矩阵的大小，不能再快啦！

• 空间复杂度: $O(1)$ 在我们的代码实现中，我们是边计算边输出的，并没有把整个 $m \times m$ 的矩阵存储在内存里。我们只需要几个变量来保存当前的行号、列号等信息。所以，除了输出本身占用的空间，我们几乎没有使用额外的内存，空间复杂度是 $O(1)$，非常节省空间的说！

知识点总结

这道题真是又酷又有趣，我们来总结一下学到了什么吧，喵~

1. 阿达马矩阵 (Hadamard Matrix): 我们构造出的这种矩阵是一种特殊的方阵，它的行（和列）向量两两正交。它在通信（比如题目的CDMA）、信号处理和纠错码等领域有重要应用。

2. 分治与递归构造: “从小的解构造出大的解”是一种非常强大的算法思想。本题中从 $H_n$ 构造 $H_{2n}$ 的方法就是分治思想的完美体现。

   $$H_{2n} = \begin{pmatrix} H_n & H_n \\ H_n & -H_n \end{pmatrix}$$

3. 位运算的魔力: 这道题最惊艳的地方莫过于发现了构造与位运算之间的深刻联系。popcount(i & j) 这个简洁的公式背后隐藏着递归构造的本质。在处理与2的幂相关的问题时，多往位运算的方向想一想，常常会有意想不到的收获！

4. 观察与归纳: 从小数据中寻找规律，然后推广到一般情况，是解决构造题的常用技巧。就像我一样，保持好奇心和敏锐的观察力，就能发现问题的奥秘！

希望这篇题解能帮到你，如果还有什么问题，随时可以再来问我哦！加油，喵~