题解 | 二维斐波那契数列

发现答案等于二维路径计数，可以直接用组合数计算，复杂度

#include <iostream>
using namespace std;

const int MOD = 1e9 + 7;

using ll = long long;

ll Pow(ll a, int b) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

ll Inv(ll a) {
    return Pow(a, MOD - 2);
}

ll Fac(int n) {
    ll res = 1;
    for (int i = 2; i <= n; i++) {
        res = res * i % MOD;
    }
    return res;
}

int n;
int m;

void Solve() {
    cin >> n >> m;
    n--;
    m--;
    cout << Fac(n + m) * Inv(Fac(n) * Fac(m) % MOD) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
    return 0;
}