\

\quad \quad \quad \quad C n m = n ! m ! (N − M)! C_n^m=\frac{n! }{m! (n-m)! } Cnm=m! N – (m)! n!

Combination number is closely related to Yang Hui triangle. Every number on Yang Hui’s triangle is equal to the sum of its upper left and upper right (except the boundary)



The NTH NTH row, the MTH MTH row is, that’s Cn, m C_n^m, Cnm (starting at 0, 0, 0)

Therefore, the following recursive formula can be used to solve the Yang Hui triangle or combination number in the future:

Code:

const int N = 2000 + 5;
const int MOD = (int)1e9 + 7;
int comb[N][N];/ / comb [n] [m] is C (n, m)
void init(a)
{
    for(int i = 0; i < N; i ++)
    {
        comb[i][0] = comb[i][i] = 1;
        for(int j = 1; j < i; j ++)
        {
            comb[i][j] = comb[i- 1][j] + comb[i- 1][j- 1]; comb[i][j] %= MOD; }}}Copy the code

But this is O (n2) O (n^2) O (n^2) O (n^2), is there an easier one? There must be, because we learned inverse numbers, so we can just solve:

Code:

ll fac[N], invn[N], invfac[N];

int init(a)
{
    fac[0] = fac[1] = invfac[0] = invfac[1] = invn[0] = invn[1] = 1;
    for (int i = 2; i <= 5000005; ++i)
    {
        fac[i] = fac[i - 1] * i % mod;
        invn[i] = (mod - mod / i) * invn[mod % i] % mod; // inverse linear recursive formula
        invfac[i] = invfac[i - 1] * invn[i] % mod; }}ll comb(ll n, ll m)
{
    if (m > n)
        return 0;
    if (m < 0 || n < 0)
        return 0;
    ll res = fac[n];
    res = res * invfac[n - m] % mod;
    res = res * invfac[m] % mod;
    return res;
}
Copy the code