# Combination

也就是C n取k,由公式直接計算

  n        n!
C   =  -----------
  k    (n-k)!*(k)!

Code

int C(int n,int k){
    int top=1,down=1;
    
    for(int i=n;i>n-k;i--) top*=i;
    for(int i=k;i>0;i--) down*=i;
    
    return top/down;
}

### 加速和避免溢位的方法:一邊乘一邊除
Code

int C(int n,int k){
    int ans=1;

    for(int x=n,y=1; x>n-k || y<=k; x--,y++){
        if(x>n-k) ans*=x;
        if(y<=k) ans/=y;
    }
    return ans;
}

如果要把答案取餘數的話就比較麻煩了,要用到費馬小定理
### 模逆元

因為取餘數不可用在除法上,所以對於我們的公式就要改成

         1               1
n! *  -------  %m  *  -------  %m
      (n-k)!             k!

但要怎麼計算倒數取模呢?這時候費馬小定理就派上用場了
## 費馬小定理
定義: 對於任意正整數a和質數p

a^p-1 ≡ 1 (mod p)

a^p-1 %p == 1 %p

像是

(a=2,p=5) 2^5-1^%5=16%5=1
(a=3,p=5) 3^5-1^%5=81%5=1
(a=4,p=3) 4^3-1^%3=16%3=1

所以我們想要求1/a可以把費馬小定理的兩邊同除a

a^p-1^/a ≡ 1/a (mod p)

a^p-2^ ≡ 1/a (mod p)

所以inv(a)≡a^p-2^(mod p),這樣就解決了我們的問題點:<b>倒數取模</b>

公式:

  n              m-2         m-2
C   =  n! * (n-k)!   *  %m  k!    %m
  k

次方計算可以用快速冪,階乘和反乘階可以預處理,要用的時候直接拿就好了
Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define MAXN 100

const int mod = 1e9+7;
int f[MAXN], inv[MAXN];

int powf(int a,int b){
    int ans = 1;
    while(b){
        if(b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

int C(int a,int b){
    if(a < b) return 0;
    return f[a] * inv[b] % mod * inv[a - b] % mod;
}

signed main(){
    //預處理
    f[0] = inv[0] = 1;
    for(int i = 1 ;i < MAXN; i++){
        f[i] = (f[i - 1] * i) % mod;  //i的階乘
        inv[i] = powf(f[i], mod - 2);  //i的反階乘
    }
    
    int n,k;
    cin >> n >> k;
    cout << C(n, k);
}