【阶乘逆元】【线性求逆元】【组合计数】牛妹的数学难题

本文已参与「新人创作礼」活动，一起开启掘金创作之路。

⭐️前置知识⭐️

a×b≡1(mod  p)a \times b \equiv 1 ( mod\,\,p)a×b≡1(modp),可以称a是b在模p情况下的逆元.

逆元其实就是可以看作倒数

方式一:

通过费马小定理求逆元：

当p为素数，并且gcd(a,p)=1时，我们有ap−1≡1(mod p)a^{p−1}≡1(mod\ p)ap−1≡1(mod p)。

那么就有ap−2×a≡1(mod p)a^{p−2}×a≡1(mod\ p)ap−2×a≡1(mod p)，则a的逆元就是ap−2a^{p−2}ap−2 下面ksm函数为快速幂

方式二：

通过式子1(n+1)!×(n+1)=1n!\frac{1}{(n+1)!}\times (n+1)=\frac{1}{n!}(n+1)!1​×(n+1)=n!1​倒推接近线性求阶乘逆元

1(n+1)!\frac{1}{(n+1)!}(n+1)!1​其实就可以看作(n+1)!{(n+1)!}(n+1)!的逆元

求[1,N−1][1,N-1][1,N−1]关于mod的逆元时，可以做到在O(N)O(N)O(N)时间内解决

设模数为p

对于当前的i，设p=k×i+rp=k×i+rp=k×i+r,则

k×i+r≡0  (mod  p)k×i×(i−1×r−1)+r×(i−1×r−1)≡0  (mod  p)k×r−1+i−1≡0  (mod  p)i−1≡−k×r−1  (mod  p)i−1≡−⌊pi⌋×r−1  (mod  p)\begin{aligned} k \times i + r & \equiv 0 &\,\,(mod \,\, p) \\ k \times i \times ( i^{-1} \times r ^{-1}) + r \times (i^{-1} \times r^{-1}) &\equiv 0 &\,\,( mod \,\, p) \\ k \times r^{-1} + i ^ {-1} & \equiv 0 &\,\, (mod \,\, p)\\ i^{-1} & \equiv -k \times r^{-1} &\,\, (mod \,\, p) \\ i^{-1} & \equiv - \left \lfloor \frac{p}{i}\right \rfloor \times r^{-1} &\,\,(mod\,\,p) \end{aligned}k×i+rk×i×(i−1×r−1)+r×(i−1×r−1)k×r−1+i−1i−1i−1​≡0≡0≡0≡−k×r−1≡−⌊ip​⌋×r−1​(modp)(modp)(modp)(modp)(modp)​

注意： inv[1]inv[1]inv[1]一定要初始化为1，需要从2开始递推，不能从1开始递推

同时可以通过线性求逆元求阶乘逆元：

只需要再将逆元用类似阶乘的形式乘起来即可，求得的inv[i]即为i!i!i!的逆元

CnmC_n^mCnm​计算

⭐️方式一：公式计算 计算都是在逆元或者阶乘基础上计算的 Cnm=n!m!∗(n−m)!C_n^m = \frac{n!}{m!*(n-m)!}Cnm​=m!∗(n−m)!n!​

⭐️方式二：递推方式

需要建表,所以如果计算范围比较大时需要的空间也大

递推公式 ： Cnm=Cn−1m+Cn−1m−1C_n^m = C_{n-1}^{m} + C_{n-1}^{m-1}Cnm​=Cn−1m​+Cn−1m−1​