常規的解法就不多加贅述了，如（分子/分母，邊乘邊除），本文講述以下方法：
遞推法
了解楊輝三角、二項式、組合數之間的聯系
時間復雜度 $O(n^2)$
數據范圍10^4
乘法逆元
$C_n^m=\frac{n!}{m!(n?m)!}$
數據較大，運用乘法逆元+快速冪
$階乘O（n）,快速冪O（log(n)），總O（log(n)）$
數據范圍10^6
盧卡斯定理
$C_n^m=C_{\frac{n}{p}}^{\frac{m}{p}}?C_{n\%p}^{m\%p}\%p$
用于n,m比較大，p比較小，分解+乘法逆元求組合數法。
時間復雜度： $O(n?lo{g}_{2}n)$
使用范圍（大概）： n , m < = 10^18， p < = 10^6,

遞推法 10^4

$C_n^m=C_{n?1}^m+C_{n?1}^{m?1}$

（從n個里面選m個等同于，選最后一個+不選最后一個）

• 楊輝三角第n行是$(a+b{)}^n$展開的系數

• 楊輝三角的遞推和組合數相同（左上+上）

• 高中數學二項式的展開$(a+b{)}^n={\sum }_{i=0}^n{C}_n^i{a}^i{b}^{n?i}$

---

綜上，更能體會組合數和楊輝三角直接的千絲萬縷

代碼

時間復雜度（$n^2$）,n,m<=10^4

#include<bits/stdc++.h>
using namespace std;
int main()
{int a[100][100],n=100;a[0][0]=1;for(int i=1;i<=n;i++)for(int j=0;j<=i;j++){a[i][j]=a[i-1][j]+a[i-1][j-1];}cout<<a[5][2]<<'\n';
}

乘法逆元 10^6

關于乘法逆元可以看 2024ccpc全國邀請賽（鄭州） 補題（乘法逆元）

• 不要想著邊乘邊除就不需要乘法逆元了。這樣看似能夠整除，但在運算過程中遇到取模，此后就不能保證精確

a mod b (b為質數)，由費馬小定理得，a 的逆元是 $a^{b?2}$

• 為方便計算用公式

$$C_n^m=\frac{n!}{m!(n?m)!}$$

代碼

$階乘O（n）,快速冪O（log(n)），總O（log(n)）$ n,m<=10^6

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e8,mod=1e9+7;
int a[N];// 階乘%mod,注意N,根據題目修改，不然可能時間超限
int qpow(int a,int b,int c)//快速冪
{int ans=1;while(b){if(b&1) ans= ans*a%c;a=a*a%c,b/=2;}return ans;
}
int C(int n,int m)//排列  從n個里面選m個
{if(m>n) return 0;return a[n]*qpow(a[n-m]*a[m]%mod,mod-2,mod)%mod;//！！！！//pow(a,b,c)  a^b過程中%c
}
signed main()
{a[0]=1;for(int i=1;i<=N;i++)a[i]=i*a[i-1]%mod;cout<<C(10,3);
}

盧卡斯定理 $10^{18}mod10^6$

用于n,m比較大，p比較小

$$C_n^m=C_{\frac{n}{p}}^{\frac{m}{p}}?C_{n\%p}^{m\%p}\%p$$
可以逐層分解

代碼

使用范圍（大概）： n , m < = 10^18， p < = 10^6,

時間復雜度： $O(n?lo{g}_{2}n)$

//qpow 快速冪        return ans;
//C    組合數（逆元） return a[n]*qpow(a[n-m]*a[m]%mod,mod-2,mod)%mod;
//a[N] 階乘
int lucas(int n,int m)//在原來基礎上加上lucas函數，遞歸求解
{if(m==0)return 1;return lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod;
}
signed main()
{a[0]=1;for(int i=1;i<=N;i++)a[i]=i*a[i-1]%mod;cout<<lucas(10,3);//直接調用lucas
}

分解質因數

待補……