题解 | 二维斐波那契数列 求逆元

#include <stdio.h>
#include <stdlib.h>

#define MOD 1000000007
#define MAX_N 2000  // 因为 n,m ≤ 1000，所以 n+m-2 ≤ 1998

// 全局数组：存储阶乘和阶乘的逆元
long long fact[MAX_N + 1];      // fact[i] = i! mod MOD
long long inv_fact[MAX_N + 1];  // inv_fact[i] = (i!)^(-1) mod MOD

// 快速幂计算：计算 base^exp mod MOD
long long mod_pow(long long base, long long exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }
    return result;
}

// 预处理函数：计算所有需要的阶乘和逆元
void precompute() {
    // 1. 计算阶乘：fact[i] = i! mod MOD
    fact[0] = 1;  // 0! = 1
    for (int i = 1; i <= MAX_N; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    
    // 2. 计算阶乘的逆元
    // 方法：先计算最大阶乘的逆元，然后递推计算其他的
    inv_fact[MAX_N] = mod_pow(fact[MAX_N], MOD - 2);  // 使用费马小定理
    
    // 递推公式：inv_fact[i] = inv_fact[i+1] * (i+1) mod MOD
    for (int i = MAX_N - 1; i >= 0; i--) {
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
    }
}

// 计算组合数 C(n, k) = n! / (k! * (n-k)!)
long long comb(int n, int k) {
    if (k < 0 || k > n) return 0;  // 无效输入
    
    // 使用预计算的阶乘和逆元：
    // C(n,k) = fact[n] * inv_fact[k] * inv_fact[n-k] mod MOD
    long long result = fact[n];
    result = (result * inv_fact[k]) % MOD;
    result = (result * inv_fact[n - k]) % MOD;
    return result;
}

int main() {
    // 第一步：预处理（只需要执行一次）
    precompute();
    
    // 第二步：读取输入
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 第三步：计算答案
    // 二维斐波那契数列 a(n,m) = C(n+m-2, n-1)
    int total_steps = n + m - 2;  // 从(1,1)到(n,m)的总步数
    int down_steps = n - 1;       // 需要向下走的步数
    
    long long answer = comb(total_steps, down_steps);
    
    // 第四步：输出结果
    printf("%lld\n", answer);
    
    return 0;
}