「Nhk R2」熊与二进制 - 题解

标签与难度

标签: 数学, 组合数学, 二项式定理, 位运算, 快速幂, 计数 难度: 2000

题目大意喵~

主人你好呀~ 这道题给了我们两个神奇的函数，需要我们计算两个复杂的求和式，喵！

首先定义了两个函数：

1. $g(i) = i \oplus (i-1)$，这里的 $\oplus$ 是按位异或操作。
2. $f(i)$ 是 $g(i)$ 的二进制表示中，数字 1 的个数 (也就是 popcount)。

然后，我们需要计算下面两个式子的值，并对一个质数 $p$ 取模：

1. 第一个求和：

   $$\text{Ans}_1 = \left(\sum_{i=1}^{2^n-1} \binom{n}{f(i)}\right) \pmod{p}$$

2. 第二个求和：

   $$\text{Ans}_2 = \left(\sum_{i=1}^{2^n-1} f(i) \cdot g(i) \cdot \binom{n}{f(i)}\right) \pmod{p}$$

输入是 $n$ 和 $p$，我们需要输出这两个答案，呐。

解题思路分析

这道题看起来好多数学符号，有点吓人呢，喵~ 但是别怕，只要我们像小猫咪一样，一步一步、耐心地拆解它，就能发现其中的奥秘啦！

Step 1: 揭开 $f(i)$ 的神秘面纱~

我们先来研究一下 $g(i) = i \oplus (i-1)$ 这个式子。这是一个非常经典的位运算技巧哦！

我们来举个例子看看，比如 $i=12$。 它的二进制是 $(1100)_2$。 那么 $i-1 = 11$，二进制是 $(1011)_2$。

把它们做异或操作：

  1100  (i=12)
^ 1011  (i-1=11)
------
  0111  (g(12)=7)

我们发现，从 $i$ 到 $i-1$，其实就是把 $i$ 二进制表示中最右边的那个 1 变成 0，然后它右边的所有 0 都变成 1。

设 $i$ 的二进制表示中，最低位的 1 在第 $k$ 位（从0开始计数），那么 $i$ 的形式就是 ...1 后面跟着 $k$ 个 0。 $i = (\dots 1 \underbrace{00\dots0}_{k \text{ 个}})_2$$i-1 = (\dots 0 \underbrace{11\dots1}_{k \text{ 个}})_2$ （更高位的 ... 部分是完全一样的）

当它们异或时，高位部分因为相同，异或结果为 0。而从第 $k$ 位开始往右，就变成了： $1\underbrace{00\dots0}_{k} \oplus 0\underbrace{11\dots1}_{k} = 1\underbrace{11\dots1}_{k+1 \text{ 个}}$ 这个结果是 $2^{k+1}-1$ 呀！

所以，$g(i) = 2^{k+1}-1$，其中 $k$ 是 $i$ 的二进制表示中末尾 0 的个数。这个 $k$ 通常被称为 ctz(i) (Count Trailing Zeros)。

那么 $f(i)$ 是什么呢？$f(i)$ 是 $g(i)$ 二进制中 1 的个数。一个形如 $2^{m}-1$ 的数，它的二进制表示就是 $m$ 个连续的 1。所以，$f(i) = \text{popcount}(2^{k+1}-1) = k+1$。

第一个关键发现：$f(i) = \text{ctz}(i) + 1$。原来 $f(i)$ 的值只和 $i$ 末尾有多少个连续的 0 有关，是不是很简单了喵？

Step 2: 第一个求和，变身！

现在我们来解决第一个求和 Ans1：

$$\text{Ans}_1 = \sum_{i=1}^{2^n-1} \binom{n}{f(i)}$$

直接遍历 $i$ 从 $1$ 到 $2^n-1$ 肯定是不行的，因为 $n$ 太大了。但是我们有了关于 $f(i)$ 的新发现，可以换个思路！我们可以按照 $f(i)$ 的值来分类计算，呐。

$f(i)$ 的值是 $\text{ctz}(i)+1$。当 $i$ 在 $[1, 2^n-1]$ 范围内时，$\text{ctz}(i)$ 的取值范围是 $[0, n-1]$。所以 $f(i)$ 的取值范围就是 $[1, n]$。

我们把求和式改写成：

$$\text{Ans}_1 = \sum_{v=1}^{n} \left( \text{有多少个 } i \text{ 满足 } f(i)=v \right) \cdot \binom{n}{v}$$

现在的问题是，对于一个给定的 $v \in [1, n]$，有多少个 $i \in [1, 2^n-1]$ 使得 $f(i)=v$ 呢？ $f(i) = v \implies \text{ctz}(i)+1 = v \implies \text{ctz}(i) = v-1$。 一个数 $i$ 的末尾有 $v-1$ 个 0，意味着它可以被写作 $i = m \cdot 2^{v-1}$，其中 $m$ 是一个奇数。

我们需要统计满足 $1 \le m \cdot 2^{v-1} \le 2^n-1$ 的奇数 $m$ 的个数。 这等价于 $1 \le m \le \lfloor \frac{2^n-1}{2^{v-1}} \rfloor = 2^{n-(v-1)}-1 = 2^{n-v+1}-1$。 我们需要在 $[1, 2^{n-v+1}-1]$ 这个区间里找奇数。 这个区间里的奇数有 $1, 3, 5, \dots, 2^{n-v+1}-1$。 个数是 $\frac{(2^{n-v+1}-1) - 1}{2} + 1 = 2^{n-v}$ 个。

好耶！我们找到了满足 $f(i)=v$ 的 $i$ 的个数是 $2^{n-v}$ 个。 代入 Ans1 的求和式：

$$\text{Ans}_1 = \sum_{v=1}^{n} 2^{n-v} \binom{n}{v}$$

这个式子是不是很眼熟？让我想想... 啊！是二项式定理！ 根据二项式定理： $(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$。 我们令 $x=1, y=2$，得到： $(1+2)^n = \sum_{v=0}^{n} \binom{n}{v} 1^v 2^{n-v} = \sum_{v=0}^{n} \binom{n}{v} 2^{n-v}$$3^n = \binom{n}{0}2^{n-0} + \sum_{v=1}^{n} \binom{n}{v} 2^{n-v} = 2^n + \text{Ans}_1$

所以，我们得到了 Ans1 的最终公式：

$$\text{Ans}_1 = 3^n - 2^n$$

Step 3: 第二个求和，看我的喵喵拳！

接下来是更复杂的 Ans2：

$$\text{Ans}_2 = \sum_{i=1}^{2^n-1} f(i) \cdot g(i) \cdot \binom{n}{f(i)}$$

我们继续使用按 $f(i)$ 的值分类的魔法！

$$\text{Ans}_2 = \sum_{v=1}^{n} \left( \sum_{i: f(i)=v} g(i) \right) \cdot v \cdot \binom{n}{v}$$

最棒的是，我们之前发现，对于所有满足 $f(i)=v$ 的 $i$，它们对应的 $g(i)$ 的值是恒定的！ 因为 $f(i)=v \implies \text{ctz}(i) = v-1 \implies g(i) = 2^{v}-1$。

所以内层的求和 $\sum_{i: f(i)=v} g(i)$ 就变成了： $(\text{满足 } f(i)=v \text{ 的 } i \text{ 的个数}) \times (2^v-1)$ 我们已经知道这个个数是 $2^{n-v}$。 所以 Ans2 的式子可以化简为：

$$\text{Ans}_2 = \sum_{v=1}^{n} \left( 2^{n-v} \cdot (2^v-1) \right) \cdot v \cdot \binom{n}{v}$$

展开括号，得到：

$$\text{Ans}_2 = \sum_{v=1}^{n} (2^n - 2^{n-v}) \cdot v \cdot \binom{n}{v}$$

再把它拆成两个部分：

$$\text{Ans}_2 = \underbrace{2^n \sum_{v=1}^{n} v \binom{n}{v}}_{S_A} - \underbrace{\sum_{v=1}^{n} v \binom{n}{v} 2^{n-v}}_{S_B}$$

现在我们来分别打败 $S_A$ 和 $S_B$ 这两个小怪兽！

计算 $S_A$: 我们需要用到一个组合恒等式：$v \binom{n}{v} = n \binom{n-1}{v-1}$。 这个很好证明的喵：$v \frac{n!}{v!(n-v)!} = \frac{n!}{(v-1)!(n-v)!} = n \frac{(n-1)!}{(v-1)!(n-1-(v-1))!} = n \binom{n-1}{v-1}$。 所以： $\sum_{v=1}^{n} v \binom{n}{v} = \sum_{v=1}^{n} n \binom{n-1}{v-1} = n \sum_{v=1}^{n} \binom{n-1}{v-1}$ 令 $j=v-1$，求和就变成了 $n \sum_{j=0}^{n-1} \binom{n-1}{j}$。 这个求和就是 $(1+1)^{n-1} = 2^{n-1}$。 所以 $\sum_{v=1}^{n} v \binom{n}{v} = n \cdot 2^{n-1}$。 代入 $S_A$： $S_A = 2^n \cdot (n \cdot 2^{n-1}) = n \cdot 2^{2n-1}$。

计算 $S_B$: $S_B = \sum_{v=1}^{n} v \binom{n}{v} 2^{n-v}$ 同样使用 $v \binom{n}{v} = n \binom{n-1}{v-1}$： $S_B = \sum_{v=1}^{n} n \binom{n-1}{v-1} 2^{n-v} = n \sum_{v=1}^{n} \binom{n-1}{v-1} 2^{n-v}$ 令 $j=v-1$，则 $v=j+1$。 $S_B = n \sum_{j=0}^{n-1} \binom{n-1}{j} 2^{n-(j+1)} = n \sum_{j=0}^{n-1} \binom{n-1}{j} 2^{(n-1)-j}$ 这个求和又是二项式定理的形式！是 $(1+2)^{n-1} = 3^{n-1}$。 所以 $S_B = n \cdot 3^{n-1}$。

最后合体！ 我们把 $S_A$ 和 $S_B$ 的结果放回 Ans2 的表达式：

$$\text{Ans}_2 = S_A - S_B = n \cdot 2^{2n-1} - n \cdot 3^{n-1}$$

任务完成！我们得到了两个简洁的公式，只需要用快速幂来计算就好啦，喵~

代码实现

下面是我根据上面的思路，重新整理的一份代码哦~ 希望能帮到主人！

#include <iostream>

// 使用 __int128 来处理可能很大的 n * 2^(2n-1) 等中间结果，避免溢出
using int128 = __int128;

// 快速幂函数，用于计算 (base^exp) % mod
// exp 可以是很大的数，所以用 int128
long long power(long long base, int128 exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            res = (int128)res * base % mod;
        }
        base = (int128)base * base % mod;
        exp /= 2;
    }
    return res;
}

void solve() {
    long long n, p;
    std::cin >> n >> p;

    // --- 计算第一个答案 Ans1 = 3^n - 2^n ---
    
    // 因为 p 是质数，根据费马小定理 a^(p-1) ≡ 1 (mod p)
    // 所以 a^n ≡ a^(n % (p-1)) (mod p)
    // 为了防止 n % (p-1) == 0 的情况，我们写成 (n - 1) % (p-1) + 1
    // 但其实直接对大数 n 求模也是可以的，因为 (a*b)%m = ((a%m)*(b%m))%m
    // 快速幂内部的循环已经处理了这一点，所以直接传 n 即可
    
    long long term1_ans1 = power(3, n, p);
    long long term2_ans1 = power(2, n, p);
    
    long long ans1 = (term1_ans1 - term2_ans1 + p) % p;

    // --- 计算第二个答案 Ans2 = n * 2^(2n-1) - n * 3^(n-1) ---

    // 计算第一项: n * 2^(2n-1)
    long long n_mod_p = n % p;
    int128 exp1_ans2 = (int128)2 * n - 1;
    if (exp1_ans2 < 0) exp1_ans2 = 0; // n=0 的特殊情况，虽然题目中 n>=1
    long long term1_ans2 = power(2, exp1_ans2, p);
    term1_ans2 = (n_mod_p * term1_ans2) % p;

    // 计算第二项: n * 3^(n-1)
    int128 exp2_ans2 = n - 1;
    if (exp2_ans2 < 0) exp2_ans2 = 0; // n=0 的情况
    long long term2_ans2 = power(3, exp2_ans2, p);
    term2_ans2 = (n_mod_p * term2_ans2) % p;
    
    long long ans2 = (term1_ans2 - term2_ans2 + p) % p;

    std::cout << ans1 << " " << ans2 << std::endl;
}

int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

复杂度分析

• 时间复杂度: 对于每个测试用例，我们只进行了几次快速幂运算。快速幂的时间复杂度是 $O(\log E)$，其中 $E$ 是指数。在这里，指数最大是 $2n-1$ 级别，所以单次计算是 $O(\log n)$。总的时间复杂度就是 $O(T \cdot \log n)$，非常快哦！
• 空间复杂度: 我们只用了几个变量来存储中间结果，没有使用额外的数组或者数据结构。所以空间复杂度是 $O(1)$，非常节省内存呢，喵~

知识点总结

这道题虽然伪装成了一道复杂的求和题，但其实是一只可爱的数学纸老虎！我们用到的知识点有：

1. 位运算技巧: 理解 $i \oplus (i-1)$ 的效果是解题的第一步，它能帮我们快速找到 $g(i)$ 和 $f(i)$ 的规律。
2. 组合恒等式: $v \binom{n}{v} = n \binom{n-1}{v-1}$ 这个恒等式是化简求和式的利器。
3. 二项式定理: 最终的化简都归结于二项式定理 $(x+y)^n = \sum \binom{n}{k}x^k y^{n-k}$ 的应用，这是组合数学中的核心工具。
4. 分类与计数: 将复杂的求和按照某个关键变量（这里是 $f(i)$）的值进行分类，然后分别计算每一类的贡献，是一种非常有效的解题策略。
5. 模运算与快速幂: 在处理大数和求幂的计算时，快速幂是必不可少的算法，可以保证计算在允许的时间内完成。

希望这篇题解能帮到主人，如果还有不懂的地方，随时可以再来问我哦，喵~