题目信息

  • 平台:牛客
  • 题目:杨辉三角
  • 难度:简单
  • 时间限制:1 秒 / 空间限制:256M

题目描述

小 F 对杨辉三角颇有研究,他把杨辉三角第 行的数提出来,从左到右分别为 。

现在他想知道:

的值是多少,答案对 取模。

输入描述

输入一个正整数 :

输出描述

输出上述式子的值,答案对 取模。


初步思路

最大达到 ,显然无法建出杨辉三角逐项累加。必须把求和式化成闭式公式。

杨辉三角第 行的元素就是组合数:

于是问题变成计算:

这个式子可以用二项式定理处理。


公式推导

方法一:生成函数

由二项式定理:

对上式求一次导再求一次导,并代入 :

第一次求导:

第二次求导:

令 得:

又因为:

所以:

其中:

两者相加:

方法二:组合恒等式

也可以直接用组合数递推。注意到:

以及:

利用 同理可得相同结论,这里不再展开。

Note
当 时 ,公式中的 没有意义,因此代码中单独特判 。 时公式成立,结果为 。

算法分析

  • 核心:组合数求和化为闭式公式;
  • 关键技巧:二项式定理求导,提取 ;
  • 整数除法:先取模再乘以 的逆元;
  • 时间复杂度:,来自快速幂;
  • 空间复杂度:。

关于除以 2

公式中的 在取模意义下不能直接整除。注意到模数 是奇数,因此 的逆元存在:

所以:

同时,为避免 溢出( 可达 ),要先对两个因子分别取模再相乘。


代码实现

以下给出 C++、Python、Java、Go、Rust 五种语言的实现,逻辑完全一致。切换上方的标签即可对比。

#include <iostream>

using namespace std;

using ll = long long;

const ll MOD = 99824353;

// 快速幂:计算 b^e mod MOD
ll qpow(ll b, ll e) {
    ll result = 1;
    b %= MOD;

    while (e > 0) {
        if (e & 1) {
            result = result * b % MOD;
        }
        b = b * b % MOD;
        e >>= 1;
    }

    return result;
}

int main() {
    ll n;
    cin >> n;

    // 第 1 行只有 a[0] = 1,对答案没有贡献
    if (n == 1) {
        cout << 0 << '\n';
        return 0;
    }

    // 答案为 n * (n - 1) / 2 * 2^(n - 2) mod MOD
    // 先取模再乘,避免 n * (n - 1) 溢出
    ll a = (n % MOD) * ((n - 1) % MOD) % MOD;
    ll b = a * qpow(2, n - 2) % MOD;

    // 模数为奇数时,除以 2 等价于乘以 2 的逆元
    cout << b * ((MOD + 1) / 2) % MOD << '\n';

    return 0;
}

样例验证

时第 3 行为 :

与公式计算结果一致。

时第 10 行为 :

与公式结果一致。


易错点

  1. 模意义下不能直接除以 2:必须乘以逆元 。
  2. 先取模再相乘: 可达 ,直接算 会溢出 long long。
  3. 需要特判:此时求和只有一项 ,而公式含 无意义。
  4. 组合数是第 行:杨辉三角第 行对应 ,不要写成 。
  5. **快速幂的指数是 **:来自 。

总结

本题的关键是把「杨辉三角逐项求和」转化为「组合数加权求和」,再用二项式定理的两次求导得到闭式公式:

转化完成后,只需一次快速幂即可在 时间内求出答案。