B - The Circumference of the Circle （求三角形外接圆）

(a+b)%p = a%p + b%p ;
(a-b)%p = a%p - b%p ;
(a*b)%p = a%p * b%p ;
但是($\frac{a}{b}$)%p ≠ $\frac{amodp}{bmodp}$这种时候就要用到逆元
在求组合数时 C$\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ = $\frac{n!}{m!\ast (n-m)!}$ %p ≠ $\frac{n!modp}{m!\ast (n-m)!modp}$ , 求逆元的时候用到费小马定律

费小马定律

若a 与 p互质且p为质数时 ，a^(p-1)%p== 1%p ;

因为a^p-1 = a^p-2 * a , 所以a^p-2 为a 的逆元 ，即($\frac{x}{a}$)%p=(x%p)*(a^p-2%p)%p ;

求C$\left(\genfrac{}{}{0ex}{}{n}{m}\right)$%p

1. 求出所有小于n的阶乘用f[i] 表示（f[i]%p）
2. 求m! 的逆元即f[m] 的逆元 a = fastpow(f[m]，p-2) （快速幂取模）
3. 求(n-m)! 的逆元 b = fastpow(f[n-m],p-2)
4. C$\left(\genfrac{}{}{0ex}{}{n}{m}\right)$%p = f[n] * a * b ;

模板：

#include <iostream>
using namespace std ;
typedef long long ll ;
const int N=1e5+5 ;
const int mod = 998244353 ;
int f[N] ;
ll n , k , p ;
ll fastpow(ll a , ll b){
ll res = 1 ;
while(b){
if(b&1)	res=res*a%mod ;
a = a*a%mod ;
b >>= 1 ;
}
return res ;
}
int main(){
cin >>n>>k>>p ;
f[0] = f[1] = 1 ; //f[0] 也要赋值为 1 
for(ll i=2;i<=n;++i)	f[i] = f[i-1]*i%mod ;
ll ans = 0 , q = (mod+1-p)%mod ;
for(ll i=k;i<=n;++i){
ll c = f[n]*fastpow(f[i],mod-2)%mod*fastpow(f[n-i],mod-2)%mod ;//逆元法求组合数 
ll d = fastpow(p,i)*fastpow(q,n-i)%mod ; //当前概率 
ans = (ans+c*d%mod)%mod ; //求和 
}
cout << ans << endl ;
return 0 ;
}

参考及详细解说—> 逆元求组合数
还有一个其他方法求组合数的 —> 求组合数的各种方法

最后

以上就是忧伤刺猬为你收集整理的逆元法求组合数B - The Circumference of the Circle （求三角形外接圆）的全部内容，希望文章能够帮你解决逆元法求组合数B - The Circumference of the Circle （求三角形外接圆）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。