- 模逆元 (modular multiplicative inverse)【參考】
- 或稱模倒數，或者模反元素。【Wiki】
- inv[i] = i 的逆元 (% mod)
- 公式：inv[i]= – (mod / i) * inv[mod % i]
- 為避免負數取模，inv[i]= mod – ( mod / i * inv[mod % i]) % mod
- 【例子】mod = 17, inv[10] = 12
- 【例子】mod = 11, inv[3] = 4
- 【例子】mod = 1e9 + 7, inv[2] = 5e8 + 4
- 2 * (5e8 + 4) = 1e9 + 8, (1e9+8) % (1e9+7) = 1
- 【應用】可以用來快速計算 C(n, k) = n! / (k! * (n-k)!) = pre[n] * prei[k] * prei[n-k]
- 【範例】AtCoder 154F – Many Many Paths 【題解】
#include <iostream>
using namespace std;
#define ll long long
const int mod = 17, maxn = 20;
ll pre[maxn+1];
ll inv[maxn+1];
ll prei[maxn+1];
void build(int n){
pre[1] = pre[0] = 1, inv[1] = inv[0] = 1, prei[1] = prei[0] = 1;
for(int i = 2 ; i <= n ; i++){
pre[i] = pre[i-1] * i % mod;
// i 的逆元inv[i]= -(p/i) * inv[p%i] (mod p)
inv[i] = mod - (mod / i * inv[mod % i]) % mod;
prei[i] = prei[i-1] * inv[i] % mod;
}
}
ll C(int n, int k){
return pre[n] * prei[k] % mod * prei[n-k] % mod;
}
int main(){
build(maxn);
cout << inv[10] << endl;
cout << C(6, 3) << endl;
}
Post Views (since April 2021) : 1,740