CF2072F - Goodbye, Banker Life 题解

题目分析

题目给出一个用异或生成的三角形：第一行是 $k$，每一行的左右端点继承上一行，内部位置等于上一行相邻两个数的异或。对每组 $n,k$，需要输出第 $n$ 行的所有数。

关键难点是 $n$ 的总和可以达到 $10^6$，不能真的逐层生成整个三角形，否则第 $1$ 行到第 $n$ 行一共会有 $O(n^2)$ 个位置。

从暴力到正解

最直接的暴力做法是维护上一行数组，然后逐层生成下一行：

• 第 $1$ 行为 $[k]$；
• 第 $i$ 行左右端点复制上一行端点；
• 中间位置用上一行相邻两个数异或得到。

这样生成到第 $n$ 行需要处理约 $1+2+\cdots+n=O(n^2)$ 个数。当 $n=10^6$ 时完全不可行。

接下来观察异或运算。异或对每一位来说就是模 $2$ 加法，因此某个位置最终等于多少，只取决于初始的 $k$ 被“贡献”了奇数次还是偶数次：

• 如果贡献次数为奇数，这个位置是 $k$；
• 如果贡献次数为偶数，这个位置是 $0$。

和普通 Pascal 三角形一样，第 $n$ 行第 $j$ 个位置的贡献次数是组合数：

所以问题转化成：判断 $\binom{n-1}{j-1}$ 的奇偶性。

正解思路

根据 Lucas 定理在模 $2$ 下的形式：

当且仅当 $r$ 的每一个二进制 $1$ 位，都在 $N$ 的对应位置上也是 $1$。也就是说：

本题令 $N=n-1$，第 $j$ 个位置对应 $r=j-1$。于是从 $r=0$ 到 $n-1$ 枚举：

• 若 $(r \& (n-1))=r$，输出 $k$；
• 否则输出 $0$。

这样每个位置只需要 $O(1)$ 判断，总复杂度就是输出本身需要的 $O(\sum n)$。

正确性说明

首先，三角形的生成规则与 Pascal 三角形的递推形式完全一致，只是普通加法被替换成了异或。由于异或在每一个二进制位上等价于模 $2$ 加法，因此第 $n$ 行第 $j$ 个位置中，初始值 $k$ 的出现次数只需要看组合数 $\binom{n-1}{j-1}$ 的奇偶性。

如果这个组合数是偶数，偶数个相同的 $k$ 异或后为 $0$；如果是奇数，奇数个相同的 $k$ 异或后仍为 $k$。因此第 $j$ 个位置只可能是 $0$ 或 $k$。

Lucas 定理告诉我们，在模 $2$ 意义下，$\binom{N}{r}$ 为奇数当且仅当 $r$ 的每个二进制 $1$ 位都被 $N$ 包含，即 $(r \& N)=r$。算法正是按这个条件输出 $k$，否则输出 $0$，所以每个位置都与真实三角形一致。

复杂度分析

对于每个测试用例，算法枚举第 $n$ 行的 $n$ 个位置，每个位置做一次按位与判断。

• 时间复杂度：$O(n)$，所有测试用例总时间复杂度为 $O(\sum n)$。
• 空间复杂度：$O(1)$，除了输出外不需要保存整行数组。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        long long k;
        cin >> n >> k;

        // 第 n 行对应 Pascal 系数中的第 n-1 行。
        int row = n - 1;

        for (int r = 0; r < n; ++r) {
            // C(row, r) 为奇数，当且仅当 r 的 1 位都是 row 的 1 位。
            long long ans = ((r & row) == r) ? k : 0;

            if (r) cout << ' ';
            cout << ans;
        }
        cout << '\n';
    }
    return 0;
}