逆元与组合数

159 阅读 0 评论 105 点赞

我是靠谱客的博主传统灰狼，这篇文章主要介绍逆元与组合数，现在分享给大家，希望可以做个参考。

线性逆元打表

inv[i] i n v [ i ] 为模 P P （P需要是质数）意义下 $i$ 的逆元，那么有 inv[i]=(P−Pi)×inv[P i n v [ i ] = ( P − P i ) × i n v [ P % i] i ] % P P 。
写成代码如下。

ll inv[N];
inv[0] = 1; inv[1] = 1;
for(int i = 2; i < N; ++i)
inv[i] = (P - P/i) * inv[P % i] % P;

一般用于 $o (n)$ 预处理、 O(1) O ( 1 ) 求组合数。

ll inv[N], f[N];
inline ll C(int n, int m) {
return f[n] * inv[m] % P * inv[n - m] % P;
}
inv[0] = 1; inv[1] = 1; f[0] = 1; f[1] = 1;
for(int i = 2; i < N; ++i)
inv[i] = (P - P/i) * inv[P % i] % P;
for(int i = 2; i < N; ++i) {
f[i] = f[i - 1] * i % P;
inv[i] = inv[i - 1] * inv[i] % P;
}