引入根据主题给出的数据范围，自己选择方法；
方式一、c(n，k )=c ) n1，k1 ) c ) n1，k )=c ) n-1，k-1 ) c ) n，k )=c ) n1，k1 ) c
我们把n n n个元素分成了两组
第一组n1n-1n1个，第二组11个
从其中取出k k k个元素(共c(n，k ) c ) n，k k k ) n，k )种)
现在的做法有两种
从第一组中取出kk个方法是，用c(n1，k ) c(n-1，k ) c(n1，k ) k )种从第一组中取出k1k-1个，从第二组中取出11个的方法是c(n1，k1 ) )
−1)种
即 C ( n , k ) = C ( n − 1 , k ) + C ( n − 1 , k − 1 ) C(n,k)=C(n-1,k)+C(n-1,k-1) C(n,k)=C(n−1,k)+C(n−1,k−1)
例题 题面
传送门
Code #include <iostream>#include <cstdio>#include <algorithm>using namespace std;typedef long long ll;const int N = 2e3 + 10;const int MOD = 1e9 + 7;int C[N][N];void init(){ for(int i=0;i<N;++i){ for(int j=0;j<=i;++j){ if(!j) C[i][j] = 1; //不用担心越界 因为当i=0 j=0时 只会走上面那个if else C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD; } }}void solve(){ init(); int n,a,b; cin >> n; while(n--){ cin >> a >> b; cout << C[a][b] << 'n'; }}int main(){ std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); solve(); return 0;} 方式二
预处理出阶乘以及阶乘的逆元；
随后利用公式求解；
题面
传送门
Code #include <iostream>#include <cstdio>#include <algorithm>using namespace std;typedef long long ll;const int N = 1e5 + 10;ll fact[N];//fact(i) = i! % MOD;ll infact[N];//infact(i) = (i!)^{-1} % MODconst int MOD = 1e9 + 7;ll qpow(ll x,int y){ ll ret = 1,base = x; while(y){ if(y&1){ ret *= base; ret %= MOD; } y>>=1; base *= base; base %= MOD; } return ret;}int C(int a,int b){ ll ret = (1ll*fact[a]*infact[b]%MOD)*infact[a-b]; return ret % MOD;}void init(){//预处理阶乘以及逆元 //0! = 1 fact[0] = infact[0] = 1; for(int i=1,inv;i<N;++i){ fact[i] = (fact[i-1] * i) % MOD; inv = qpow(i,MOD-2); infact[i] = (infact[i-1] * inv) % MOD; }}void solve(){ init(); int n,a,b; ll ans; cin >> n; while(n--){ cin >> a >> b; cout << C(a,b) << 'n'; }}int main(){ std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); solve(); return 0;} 方式三
应用ymdyx定理；
C a b ≡ C a % p b % p C a / p b / p ( m o d p ) C_a^b equiv C_{a%p}^{b%p}C_{a/p}^{b/p} (mod p) Cab≡Ca%pb%pCa/pb/p (mod p)
题面
Code #include <iostream>#include <cstdio>#include <algorithm>using namespace std;typedef long long ll;const int N = 1e5 + 10;int p;int qpow(int x,int y){ ll ret = 1,base = x; while(y){ if(y&1){ ret *= base; ret %= p; } base *= base; base %= p; y >>= 1; } return ret%p;}int C(int a,int b){ ll ret = 1; for(int i=a,j=b;j>=1;--i,--j){ ret = ret*i%p; ret = ret*qpow(j,p-2)%p; } return ret;}int 爱笑的果汁(ll a,ll b){ if(a < p && b < p) return C(a,b); return 1ll*C(a%p,b%p) * 爱笑的果汁(a/p,b/p) % p;}void solve(){ int n; cin >> n; ll a,b; while(n--){ cin >> a >> b >> p; cout << 爱笑的果汁(a,b) << 'n'; }}int main(){ std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); solve(); return 0;} 方式四
这种方式由于需要使用高精度，因此我们先对数进行质因数分解；
题面
传送门
Code #include <iostream>#include <algorithm>#include <string>#include <vector>using namespace std;const int N = 5010;int primes[N], cnt;int sum[N];bool st[N];void get_primes(int n){ for (int i = 2; i <= n; i ++ ){ if (!st[i]) primes[cnt ++ ] = i; for (int j = 0; primes[j] <= n / i; j ++ ){ st[primes[j] * i] = true; if (i % primes[j] == 0) break; } }}//对p的各个<=a的次数算整除下取整倍数int get(int n, int p){ int res = 0; while (n){ res += n / p; n /= p; } return res;}string mul(const string &A,const int b){ if(b == 0) return "0"; string res; for(int i=A.size()-1,t=0;i>=0||t>0;--i){ if(i>=0) t+= (A[i] - '0')*b; res += (t%10) + '0'; t /= 10; } reverse(res.begin(),res.end()); return res;}int main(){ int a, b; cin >> a >> b; get_primes(a); for (int i = 0; i < cnt; i ++ ){ int p = primes[i]; sum[i] = get(a, p) - get(a - b, p) - get(b, p); } string res = "1"; for (int i = 0; i < cnt; i ++ ) for (int j = 0; j < sum[i]; j ++ ) res = mul(res, primes[i]); cout << res << 'n'; return 0;}