警示后人 80pts Wa on #21
查看原帖
警示后人 80pts Wa on #21
185223
huangziqinFJ人炖蒟蒻楼主2024/4/1 14:12

这是一个很弱智的错误 QAQQAQ

在求逆元的时候 FF 函数不一定和 pkp^k 互质,所以不能用快速幂只能用exgcd

实例:

WaWa

long long init(long long n,long long m,long long p,long long pk)
{
	long long fz=F(n,p,pk),fm1=qpow(F(m,p,pk),pk-2,pk),fm2=qpow(F(n-m,p,pk),pk-2,pk); 
	long long ch=qpow(p,G(n,p)-G(m,p)-G(n-m,p),pk);
	return fz*fm1%pk*fm2%pk*ch%pk;
}

AcAc

long long ny(long long a,long long b)
{
	long long x,y; exgcd(a,b,x,y);
	return (x%b+b)%b;
}
long long init(long long n,long long m,long long p,long long pk)
{
	long long fz=F(n,p,pk),fm1=ny(F(m,p,pk)%pk,pk),fm2=ny(F(n-m,p,pk),pk);
	long long ch=qpow(p,G(n,p)-G(m,p)-G(n-m,p),pk);
	return fz%pk*fm1%pk*fm2%pk*ch%pk;
}
2024/4/1 14:12
加载中...