组合数是什么？

举个例子，有 $n$ 个小球 要你将它们取出 $m$ 个，方案数即为组合数，即 $C^m_n$

组合数计算方法1

也就是最常用的公式：$C^m_n = \frac{n!}{m!(n-m)!}$
最简单的暴力：

#define int long long
int jj(int x)
{
        sum=1;
        for (int i=2; i<=x; i++)
                sum*=i;
        return sum;
}
int solve(int n, int m)
{
        return jj(n)/(jj(m)*jj(n-m));
}
void init()
{
        cin >> n >> m;
        cout << solve(n,m);
}

但这么做不仅当要求多组数据时很慢而且当所求的数超过long long 的范围时就会爆蛋...

组合数计算方法2

递推求
怎么求？ 这时我们就要用到组合数的公理了
$C^m_n=C^{n-m}_n$
由此可以推得：
$C^m_n=C^{m-1}_{n-1}+C^{m}_{n-1}$
于是就有了下面这段代码：

#define int long long
void build()
{
        c[0][0]=c[1][0]=c[1][1]=1;//预处理
        for (int i=2; i<=2000; i++)
        {
                c[i][0]=1;
                for (int j=1; j<=2000; j++)
                        c[i][j]=c[i-1][j-1]+c[i-1][j]; //递推
        }
}
int main()
{

        build();
        cin >> n >> m;
        cout << c[n][m];
}

然后这时候我们发现，在遇到一些多组数据题时，一遍遍找答案很费劲，于是乎我们还可以做前缀和进行优化，使找答案的时间复杂度降到 $O(1)$。

例题：$\text{[NOIP2016 提高组] 组合数问题}$

这题就要用到前缀和优化，否则会T，还有毒瘤取模...
至于如何前缀和，我们可以推得：
$ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]$
于是得到下面的 $ac$ 代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 2001;
int t,k,n,m,ans[N][N],c[N][N];
void build()
{
        c[0][0]=c[1][0]=c[1][1]=1;
        for (int i=2; i<=2000; i++)
        {
                c[i][0]=1;
                for (int j=1; j<=i; j++)
                {
                        c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;//这个取模是看题解才知道的...
                        ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
                        if (!c[i][j]) ans[i][j]++;
                }
                ans[i][i+1]=ans[i][i];
        }
}
signed main()
{
        cin >> t >> k;
        build();
        for (int i=1; i<=t; i++)
        {
                cin >> n >> m;
                if (m>n) cout << ans[n][n] << endl;
                else cout << ans[n][m] << endl;
        }
}

但是我们又发现，虽然这么解查答案复杂度很小，但求组合数还是太慢，由此我们可以引出一个线性做法。

组合数计算方法3

那就是 逆元+快速幂解法。
思路：现在目标是求C(n, m) %p，p为素数（经典p=1e9+7）。
虽然有C(n, m) = n! / [m! (n - m)!]，但由于取模的性质对于除法不适用，则有
![]
(https://img-blog.csdnimg.cn/20190513133335648.png)
所以需要利用逆元把“除法”转换成“乘法”，才能借助取模的性质计算组合数。
求解 $C(n, m)$ 的步骤：

1. 通过循环，预先算好所有小于max_ number的阶乘的结果，存到 $fac[max_-number]$ 里 ( $fac[i] = i!$ )
2. 求 $m!$ 的逆元（即求 $fac[m]$ 的逆元）：根据费马小定理，$x$ $mod$ $p$ 的逆元为 $x^{p−2}$ ， 因此通过快速幂，求解 $fac[m]^{p−2} mod p$ ，记为 $M$
3. 求 $(n-m)!$ 的逆元：同理就是求解 $fac[n−m]^(p−2)$ ，记为 $NM$
4. $C(n, m) = ((fac[n] * M)$

$Code$

int quick_power(int x,int y)
{
        int res=1;
        for (; y; y=y>>1,x=(x*x)%mod)
        {
                if (y&1) res=(res*x)%mod;
        }
        return res;
}//快速幂

void init()
{
        jc[0]=1;
        for (int i=1; i<=n; i++) jc[i]=(jc[i-1]*i)%mod;

        inv[n]=quick_power(jc[n],mod-2);
        for (int i=n-1; i>=0; i--) inv[i]=(inv[i+1]*(i+1))%mod;
}//初始化

int C(int x,int y)
{
        if (y==0) return 1;
        if (x<y) return 0;
        return ((jc[x]*inv[y])%mod*inv[x-y])%mod;
}//求C

$\large{The \ end.}$