题目信息
- 平台:牛客
- 题目:杨辉三角
- 难度:简单
- 时间限制: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;
}import sys
MOD = 99824353
def qpow(base, exponent):
result = 1
base %= MOD
while exponent > 0:
if exponent & 1:
result = result * base % MOD
base = base * base % MOD
exponent >>= 1
return result
def solve():
n = int(sys.stdin.buffer.readline())
if n == 1:
print(0)
return
a = (n % MOD) * ((n - 1) % MOD) % MOD
b = a * qpow(2, n - 2) % MOD
print(b * ((MOD + 1) // 2) % MOD)
if __name__ == '__main__':
solve()import java.util.Scanner;
public class Main {
static final long MOD = 99824353L;
static long qpow(long base, long exponent) {
long result = 1;
base %= MOD;
while (exponent > 0) {
if ((exponent & 1) != 0) {
result = result * base % MOD;
}
base = base * base % MOD;
exponent >>= 1;
}
return result;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long n = scanner.nextLong();
if (n == 1) {
System.out.println(0);
return;
}
long a = (n % MOD) * ((n - 1) % MOD) % MOD;
long b = a * qpow(2, n - 2) % MOD;
System.out.println(b * ((MOD + 1) / 2) % MOD);
}
}package main
import "fmt"
const MOD int64 = 99824353
func qpow(base, exponent int64) int64 {
result := int64(1)
base %= MOD
for exponent > 0 {
if exponent&1 == 1 {
result = result * base % MOD
}
base = base * base % MOD
exponent >>= 1
}
return result
}
func main() {
var n int64
fmt.Scan(&n)
if n == 1 {
fmt.Println(0)
return
}
a := (n % MOD) * ((n - 1) % MOD) % MOD
b := a * qpow(2, n-2) % MOD
fmt.Println(b * ((MOD + 1) / 2) % MOD)
}use std::io::{self, Read};
const MOD: i64 = 99824353;
fn qpow(mut base: i64, mut exponent: i64) -> i64 {
let mut result = 1;
base %= MOD;
while exponent > 0 {
if exponent & 1 == 1 {
result = result * base % MOD;
}
base = base * base % MOD;
exponent >>= 1;
}
result
}
fn main() {
let mut input = String::new();
io::stdin().read_to_string(&mut input).unwrap();
let n: i64 = input.trim().parse().unwrap();
if n == 1 {
println!("0");
return;
}
let a = (n % MOD) * ((n - 1) % MOD) % MOD;
let b = a * qpow(2, n - 2) % MOD;
println!("{}", b * ((MOD + 1) / 2) % MOD);
}样例验证
与公式计算结果一致。
与公式结果一致。
易错点
- 模意义下不能直接除以 2:必须乘以逆元
。 - 先取模再相乘:
可达 ,直接算 会溢出 long long。 需要特判:此时求和只有一项 ,而公式含 无意义。 - 组合数是第
行:杨辉三角第 行对应 ,不要写成 。 - **快速幂的指数是
**:来自 。
总结
本题的关键是把「杨辉三角逐项求和」转化为「组合数加权求和」,再用二项式定理的两次求导得到闭式公式:
转化完成后,只需一次快速幂即可在