这是一个很弱智的错误 QAQ
在求逆元的时候 F 函数不一定和 pk 互质,所以不能用快速幂只能用exgcd
实例:
Wa
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;
}
Ac
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;
}