主人你好喵~ 这里是小猫娘的题解教室啦！

今天我们要看一道非常有趣的题目哦，它看起来像组合数，但又因为一个小小笔误，变得完全不一样了呢！让我们一起来看看这个可爱的错误会带来什么神奇的结果吧，喵~

B. Binomial Coefficients, Kind Of

---

题目大意

这道题是说，有一个叫做 akshiM 的同学，他想写一个程序来计算组合数 C(n, k)。

我们都知道，正确的组合数递推公式是 C(n, k) = C(n-1, k) + C(n-1, k-1)，对吧？

但是呢，akshiM 同学迷迷糊糊地把公式写错了，写成了：

C(n, k) = C(n, k-1) + C(n-1, k-1)

他还定义了两个边界条件：C(n, 0) = 1 和 C(n, n) = 1。

现在，我们的任务就是，根据这个 错误 的公式，来计算出一系列 (ni, ki) 对应的 C(ni, ki) 的值。因为结果可能会很大，所以我们需要对 10^9 + 7 取模哦。

输入格式有点小调皮，它会先给你一个 t，表示有 t 组查询。然后，第二行是所有的 n，第三行是所有的 k。我们要一一对应地计算出结果~

---

题解方法

看到这个奇怪的递推公式，第一反应是不是有点懵呀？没关系，小猫娘最喜欢找规律了，喵！我们来手动算几个值看看~

根据题目的约束，1 <= k < n，并且 C(n, 0) = 1。

• 当 k = 1 时： C(n, 1) = C(n, 0) + C(n-1, 0) = 1 + 1 = 2 哦？C(n, 1) 的值似乎不依赖于 n 耶！

• 当 k = 2 时： C(n, 2) = C(n, 1) + C(n-1, 1) 因为我们已经知道，对于任何大于 1 的 n，C(n, 1) 的值都是 2。所以 C(n, 1) = 2，C(n-1, 1) 也等于 2。 那么 C(n, 2) = 2 + 2 = 4。

• 当 k = 3 时： C(n, 3) = C(n, 2) + C(n-1, 2) 同理，C(n, 2) = 4，C(n-1, 2) 也等于 4。 所以 C(n, 3) = 4 + 4 = 8。

喵喵~ 主人你看！ C(n, 1) = 2 = 2^1C(n, 2) = 4 = 2^2C(n, 3) = 8 = 2^3 一个大胆的猜想出现了：C(n, k) = 2^k！

我们可以用数学归纳法来证明这个猜想是不是正确的~

1. 基础情况 (Base Case): 当 k = 1 时，我们已经算过了，C(n, 1) = 2 = 2^1。成立！
2. 归纳假设 (Inductive Hypothesis): 假设当 k = m 时，对于所有 n > m，都有 C(n, m) = 2^m 成立。
3. 归纳步骤 (Inductive Step): 我们来证明当 k = m+1 时也成立。 C(n, m+1) = C(n, m) + C(n-1, m) 根据我们的归纳假设，因为 n > m+1 和 n-1 > m，所以 C(n, m) = 2^m 并且 C(n-1, m) = 2^m。 所以，C(n, m+1) = 2^m + 2^m = 2 * 2^m = 2^(m+1)。 证明成功啦！喵~

所以，这个看似复杂的递推关系，其实结果非常简单！C(n, k) 的值只和 k 有关，n 只要满足 n > k 就行了（题目已经保证了这一点），它就是 2^k！

那么问题就转化成了：对于每个输入的 k，计算 2^k mod (10^9 + 7)。 因为 k 最大可以到 10^5，直接用循环去乘 k 次会超时，所以我们需要一个更快的计算幂的方法，那就是——快速幂！

---

题解

下面我们来一起看看这份优雅的代码是怎么实现的吧~

#include <iostream>
#include <vector>

// 这是一个快速幂函数，用来计算 (base^exp) % mod
// 对于大指数来说非常高效哦
long long power(long long base, long long exp) {
    long long res = 1;
    long long mod = 1000000007;
    base %= mod;
    while (exp > 0) {
        // 如果 exp 是奇数，就说明当前二进制位是 1
        if (exp % 2 == 1) {
            res = (res * base) % mod;
        }
        // base 自乘，为下一位做准备
        base = (base * base) % mod;
        // exp 右移一位，相当于除以 2
        exp /= 2;
    }
    return res;
}

int main() {
    // 这两行是为了让输入输出更快一点的小魔法~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;

    // 根据题目，所有的 n 在一行，所有的 k 在另一行
    // n 的值其实我们用不到，但必须读进来才能读到 k
    std::vector<int> n(t);
    std::vector<int> k(t);
    for (int i = 0; i < t; ++i) {
        std::cin >> n[i];
    }
    for (int i = 0; i < t; ++i) {
        std::cin >> k[i];
    }

    // 循环处理每一组查询
    for (int i = 0; i < t; ++i) {
        // 根据我们推导出的结论，C(n, k) 就等于 2^k
        // 调用快速幂函数计算结果
        long long result = power(2, k[i]);
        // 按格式输出，最后一位后面没有空格哦
        std::cout << result << (i == t - 1 ? "" : " ");
    }
    std::cout << "\n";

    return 0;
}

代码的逻辑非常清晰，对吧？

1. power 函数是核心，它用快速幂算法在 O(log k) 的时间里计算出 2^k。
2. main 函数里，先是读入数据。这里有个小陷阱，就是 n 和 k 是分开两行读的。虽然我们推导出 n 没用，但还是要把它读掉，这样才能正确读到 k。
3. 然后对每个 k，调用 power(2, k) 计算结果并输出。整个过程又快又准确，喵~

---

知识点介绍

这道题虽然简单，但涉及到的知识点可是非常重要的哦！

1. 递推关系与数学归纳法 (Recurrence & Induction)

• 递推关系：就是一个数列中的项可以用它前面的项来表示。这道题里的 C(n, k) = C(n, k-1) + C(n-1, k-1) 就是一个递推关系。
• 数学归纳法：是一种证明方法，特别适合用来证明和自然数有关的命题。当我们通过观察找到了一个规律（比如 C(n, k) = 2^k），就可以用数学归纳法来严格地证明它。先证明基础情况，再假设 k=m 成立，然后推导出 k=m+1 也成立。这是我们解决递推问题的强大武器！

2. 快速幂 (Binary Exponentiation)

• 用途：快速计算 (base^exp) % mod。
• 核心思想：利用指数 exp 的二进制表示。比如我们想算 2^13，13 的二进制是 1101，也就是 8 + 4 + 1。所以 2^13 = 2^8 * 2^4 * 2^1。我们可以通过不断地将底数平方（2^1 -> 2^2 -> 2^4 -> 2^8 ...）来得到这些项，然后只把指数二进制位为 1 对应的项乘起来。
• 复杂度：时间复杂度是 O(log exp)，比普通的 O(exp) 循环快得多啦！在算法竞赛中是必备技能哦。

3. 模运算 (Modular Arithmetic)

• 为什么需要：因为 2^k 会变得非常大，会超出计算机整数类型的表示范围（比如 long long）。
• 核心性质：(a + b) % m = ((a % m) + (b % m)) % m 和 (a * b) % m = ((a % m) * (b % m)) % m。这个性质允许我们在计算的每一步都取模，防止中间结果溢出，同时保证最终结果的正确性。在快速幂的每一步乘法后都取模，就是这个道理啦。

好啦，这次的题解就到这里了喵~ 主人有没有觉得，一个可爱的小错误，反而让问题变得更简单有趣了呢？下次再见啦，喵~