1.基本公式
相当于直接去求 \(\frac{1}{n!}\)
也就是说 咱们要是去求\(\frac{1}{n}\)逆元
2.怎么求逆元？
代码模板
LL exgcd(LL a,LL b,LL &x,LL &y)//扩展欧几里得算法
{
if(b==0)
{
x=1,y=0;
return a;
}
LL ret=exgcd(b,a%b,y,x);
y-=a/b*x;
return ret;
}
LL getInv(int a,int mod)//求a在mod下的逆元，不存在逆元返回-1
{
LL x,y;
LL d=exgcd(a,mod,x,y);
return d==1?(x%mod+mod)%mod:-1;
}
LL qkpow(LL a,LL p,LL mod)
{
LL t=1,tt=a%mod;
while(p)
{
if(p&1)t=t*tt%mod;
tt=tt*tt%mod;
p>>=1;
}
return t;
}
LL getInv(LL a,LL mod)
{
return qkpow(a,mod-2,mod);
}
LL inv[mod+5];
void getInv(LL mod)
{
inv[1]=1;
for(int i=2;i<mod;i++)
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
就是上面要求的