今天我学了卡特兰数，在递推求第 $n$ 项时遇到了一个问题：两个数做乘法时不爆 longlong（一个 $5\times 10^5$，另一个在模数（$10^9+7$）以内）再除以一个数，再取模应该是不爆 longlong 的呀，于是找了道板子题发现只得了 40pts，结果用逆元就全对了，我寻思着逆元不也是两个数乘起来，取模，乘一个数，再取模吗？为什么逆元对了而普通的不对呢？百思不得其解，望大佬们讲一下QWQ

40pts：

#include <bits/stdc++.h>
using namespace std;
long long f[100005];
const int mod = 1e9 + 7;
int main() {
    long long n;
    cin >> n;
    f[0] = f[1] = 1;
    for (long long i = 2; i <= n; i++) f[i] = (i * 4 - 2) * f[i - 1] / (i + 1) % mod;
    cout << f[n];
    return 0;
}

满分：

#include <bits/stdc++.h>
using namespace std;
long long f[100005];
const int mod = 1e9 + 7;
long long ksm(long long x, long long k) {
    if (k == 1)
        return x;
    long long ans = ksm(x, k >> 1);
    ans = ans * ans % mod;
    if (k & 1)
        ans = ans * x % mod;
    return ans;
}
int main() {
    long long n;
    cin >> n;
    f[0] = f[1] = 1;
    for (long long i = 2; i <= n; i++) f[i] = (i * 4 - 2) * f[i - 1] % mod * ksm(i + 1, mod - 2) % mod;
    cout << f[n];
    return 0;
}