H. Bots - 题解

比赛与标签

比赛: Bubble Cup 8 - Finals [Online Mirror] 标签: combinatorics, dp, math, number theory 难度: *1800

题目大意喵~

你好呀，指挥官！今天我们要解决一个关于机器人下棋的问题，听起来就很有趣对不对？喵~

是这样的，Sasha 和 Ira 正在开发一个双人合作游戏，有两个机器人轮流行动。这个游戏有个特点，就是每次行动后进入的状态都是全新的，绝对不会回到以前的任何一个状态。

他们发现，在最优策略下，两个机器人最终都会各自行动 N 次。为了找到这个最优策略，我们的算法需要分析所有可能的游戏状态。一个状态是“可能的”，只要在到达这个状态的过程中，没有任何一个机器人行动超过 N 次。

我们的任务就是计算一下，从游戏开始（一个初始状态）到游戏结束，总共需要分析多少种不同的状态呢？结果要对 10^9 + 7 取模哦！

输入: 一个整数 N (1 ≤ N ≤ 10^6)。

输出: 一个整数，表示可能的状态总数，模 10^9 + 7。

解题思路的奇妙旅程！

这道题看起来有点复杂，但别担心，跟着本猫娘的思路，一步一步就能解开谜题啦，喵！

步骤一：理解什么是“状态”

首先，我们要搞清楚“状态”是怎么定义的。题目说“每次行动后状态都会改变”并且“绝不回到过去的状态”。这给了我们一个重要的提示：一个状态是由到达它的独一无二的行动序列决定的。

比如说，让第一个机器人叫“小红”，第二个叫“小蓝”。那么行动序列 "红蓝" 和 "蓝红" 会到达两个不同的状态，即使最后小红和小蓝都各走了一步。

所以，我们的问题就转化成：计算所有有效行动序列的总数！

步骤二：把问题转换成网格走路

一个行动序列就是由小红（R）和小蓝（B）的行动组成的字符串。一个序列是“有效”的，当且仅当在序列的任何位置，R 的数量不超过 N，B 的数量也不超过 N。

这听起来是不是很像一个经典的网格走路问题呀？

想象一个二维网格，我们从原点 (0, 0) 出发。

• 小红（Bot 1）行动一次，相当于我们向右走一步（x 坐标 +1）。
• 小蓝（Bot 2）行动一次，相当于我们向上走一步（y 坐标 +1）。

一个行动序列就对应了网格上的一条路径。例如，序列 "RBRB" 就对应路径 (0,0) -> (1,0) -> (1,1) -> (2,1) -> (2,2)。

“有效序列”的限制条件 r <= N 和 b <= N 就意味着我们的路径不能走出由 x=N 和 y=N 围成的矩形区域。我们需要计算从 (0,0) 出发，所有能到达 (r, b)（其中 0 <= r <= N, 0 <= b <= N）的路径总数。

到达点 (r, b) 需要走 r 步向右，b 步向上，总共 r+b 步。这样的路径有多少条呢？这是一个经典的组合问题，答案是 C(r+b, r)。

所以，总状态数就是把所有有效终点 (r, b) 的路径数加起来： Total = sum_{r=0 to N} sum_{b=0 to N} C(r+b, r)

步骤三：用组合数学魔法简化公式！

直接计算这个双重求和对于 N=10^6 来说太慢啦，我们需要一点数学魔法来简化它！这里要请出我们的好朋友——曲棍球棒恒等式 (Hockey-stick Identity)！

曲棍球棒恒等式 说的是：sum_{k=r to n} C(k, r) = C(n+1, r+1)。 在帕斯卡三角中，对角线上的一列数求和，结果等于下一行拐角处的那个数，形状就像个曲棍球棒，超可爱的说！

1. 简化内层求和: 我们先看 sum_{b=0 to N} C(r+b, r)。 这一串是 C(r, r) + C(r+1, r) + C(r+2, r) + ... + C(r+N, r)。 完美符合曲棍球棒恒等式！这里 k 从 r 变到 r+N。所以结果是 C((r+N)+1, r+1) = C(r+N+1, r+1)。

2. 简化外层求和: 现在我们的总和变成了 Total = sum_{r=0 to N} C(r+N+1, r+1)。 为了方便观察，我们利用 C(n, k) = C(n, n-k) 把它变个形： C(r+N+1, r+1) = C(r+N+1, (r+N+1) - (r+1)) = C(r+N+1, N)。 所以 Total = sum_{r=0 to N} C(r+N+1, N)。 展开看看：C(N+1, N) + C(N+2, N) + C(N+3, N) + ... + C(2N+1, N)。

3. 再次使用曲棍球棒恒等式: 这个和式 sum_{k=N+1 to 2N+1} C(k, N) 又可以用曲棍球棒恒等式啦！ 但是，等一下喵！恒等式要求求和从 C(N, N) 开始，而我们的和是从 C(N+1, N) 开始的。我们少加了一个 C(N, N)！ 没关系，我们把它加上再减掉就好啦： Total = (sum_{k=N to 2N+1} C(k, N)) - C(N, N) 括号里的部分现在可以用恒等式了，结果是 C((2N+1)+1, N+1) = C(2N+2, N+1)。 而 C(N, N) = 1。

所以，最终的魔法咒语就是： Total = C(2N+2, N+1) - 1

步骤四：计算组合数

要计算 C(n, r) % p，我们使用公式 n! / (r! * (n-r)!)。在模运算下，除法要变成乘以模逆元。 因为模数 10^9 + 7 是个质数，我们可以用费马小定理 a^(p-2) ≡ a⁻¹ (mod p) 来求逆元。 为了效率，我们可以预处理出 1! 到 (2N+2)! 的阶乘和阶乘的逆元，这样每次计算组合数就是 O(1) 的啦！

代码实现，上菜喵！

#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) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

// 使用费马小定理计算 n 的模逆元
long long modInverse(long long n) {
    long long mod = 1000000007;
    return power(n, mod - 2);
}

// N 最大是 10^6，所以 2*N+2 最大约 2*10^6+2，数组要开足够大
const int MAX_FACT_N = 2000003;
long long fact[MAX_FACT_N];
long long invFact[MAX_FACT_N];

// 预处理阶乘和阶乘的逆元，避免重复计算，超级高效！
void precompute_factorials(int n) {
    long long mod = 1000000007;
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
    }
    // 先用快速幂求出最大数的阶乘逆元
    invFact[n] = modInverse(fact[n]);
    // 然后倒着推回来，利用 (inv(k!)) = (inv((k+1)!)) * (k+1)
    for (int i = n - 1; i >= 0; i--) {
        invFact[i] = (invFact[i + 1] * (i + 1)) % mod;
    }
}

// 使用预处理的值，O(1) 时间计算 C(n, r) % p
long long nCr_mod_p(int n, int r) {
    long long mod = 1000000007;
    if (r < 0 || r > n) {
        return 0;
    }
    // C(n,r) = n! * inv(r!) * inv((n-r)!)
    return (((fact[n] * invFact[r]) % mod) * invFact[n - r]) % mod;
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 预处理阶乘到 2*n+2
    precompute_factorials(2 * n + 2);

    // 套用我们推导出的终极公式！
    long long total_states = nCr_mod_p(2 * n + 2, n + 1);
    
    // 别忘了最后那个小小的 -1 呀
    total_states = (total_states - 1 + 1000000007) % 1000000007;

    std::cout << total_states << std::endl;

    return 0;
}

复杂度分析

• 时间复杂度: O(N + log(mod)) 的说。

  • precompute_factorials 函数需要 O(N) 的时间来计算所有阶乘，以及 O(log(mod)) 的时间来计算一次模逆元，然后 O(N) 的时间来递推所有阶乘逆元。所以预处理总共是 O(N + log(mod))。
  • main 函数中的 nCr_mod_p 调用是 O(1) 的。
  • 所以总时间复杂度由预处理主导，是 O(N + log(mod))。

• 空间复杂度: O(N) 的说。

  • 我们需要两个数组 fact 和 invFact 来存储预处理的结果，大小都和 N 相关，具体是 2*N+2，所以空间复杂度是 O(N)。

知识点与总结

这道题是一次非常有趣的数学探险呢，喵！我们来总结一下这次旅程的收获吧：

1. 问题转化: 核心是把一个看似动态的游戏问题，转化成了一个静态的、可以计数的组合数学模型（网格路径计数）。
2. 组合恒等式: 曲棍球棒恒等式 是我们简化求和的神器！熟练掌握这类恒等式，能在解题时化繁为简，直击核心。
3. 模运算: 遇到结果可能很大的计数问题，取模是基本操作。记住，模下的除法等于乘以模逆元。
4. 预处理技巧: 当需要多次计算依赖于阶乘的组合数时，预处理阶乘和阶乘逆元是一个非常标准且高效的优化手段。

希望这篇题解能帮到你，让你也爱上用数学魔法解决算法问题的感觉！加油哦，指挥官！喵~