组合数

初始化

我们知道阶乘的定义： (i+1)! = i! * (i+1)

现在，我们对这个等式的两边同时取模逆元。根据模逆元的性质 inv(a * b) = inv(a) * inv(b) (mod p)，我们得到： inv((i+1)!) = inv(i!) * inv(i+1)

我们的目标是求 inv(i!)。所以，我们把上面的等式变形，两边同时乘以 (i+1)： inv((i+1)!) * (i+1) = inv(i!) * inv(i+1) * (i+1)

因为一个数乘以它自己的逆元等于 1（inv(x) * x ≡ 1 (mod p)），所以等式右边的 inv(i+1) * (i+1) 就等于 1。
于是我们得到了最终的关键递推关系：

inv(i!) = inv((i+1)!) * (i+1)

这个公式告诉我们：如果我们知道了 inv((i+1)!)，我们就可以用一次乘法 O(1) 的时间复杂度计算出 inv(i!)。

const int MAXN = 355;
const int MOD = 1e9 + 7;
int n;
ll fact[MAXN], invfact[MAXN];

inline ll quick_pow(ll a, ll k) {
    ll ret = 1;
    while (k) {
        if (k & 1)
            ret = ret * a % MOD;
        k >>= 1;
        a = a * a % MOD;
    }
    return ret;
}

inline ll inv(ll x) {
    return quick_pow(x, MOD - 2);
}

inline void init(int limit) {
    fact[0] = 1;
    invfact[0] = 1;
    for (int i = 1; i <= limit; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    invfact[limit] = inv(fact[limit]);
    for (int i = limit - 1; i >= 1; --i) {
        invfact[i] = (invfact[i + 1] * (i + 1)) % MOD;
    }
}

inline ll C(int n_items, int m_choices) {
    if (m_choices < 0 || m_choices > n_items)
        return 0;
    return fact[n_items] * invfact[m_choices] % MOD * invfact[n_items - m_choices] % MOD;
}

int main() {
	cin >> n;
	init(n);
}