组合计数和逆元

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;
}

就是上面要求的