题解 | 二维斐波那契数列 | 费马小定理优化组合数计算

#include <iostream>
#include <vector>
using namespace std;
using ll=long long;

const ll MOD=1e9+7;
vector<ll> fact,invFact;

// 带模快速幂
ll modqpow(ll base,ll power){
    ll res=1;
    while(power){
        if(power&1) res=res*base%MOD;
        base=base*base%MOD;
        power>>=1;
    }
    return res;
}

// 预计算，带模运算可以利用费马小定理求逆元
void initFact(int n){
    fact.resize(1+n);
    invFact.resize(1+n);
    fact[0]=1;
    for(int i=1;i<=n;++i) fact[i]=fact[i-1]*i%MOD;
    invFact[n]=modqpow(fact[n],MOD-2);
    for(int i=n-1;i>=0;--i) invFact[i]=invFact[1+i]*(1+i)%MOD;
}

// 费马小定理优化带模组合数
ll C(int n,int k){
    if(k<0 || k>n) return 0;
    return fact[n]*invFact[k]%MOD*invFact[n-k]%MOD;
}

// 费马小定理优化带模排列数
ll P(int n,int k){
    if(k<0 || k>n) return 0;
    return fact[n]*invFact[n-k]%MOD;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int rows,cols;cin>>rows>>cols;

    initFact(rows+cols-2);
    cout<<C(rows+cols-2,min(rows,cols)-1)<<'\n';

    return 0;
}

其他方法：二维DP+滚动数组优化（略）