你的exlucas板子可能是假的！

在计算

\frac{n!}{p^x}

模

p^k

的余数时（代码中令

r=p^k

），正确的计算方式如下：

CPP

	int ca(int n){
		if(n==0) return 1;
		return ca(n/p)*qp(s[r-1],n/r,r)%r*s[n%r]%r;
	}
	int sec(int n,int m,int x,int y){
		p=x,k=y,r=qp(x,y,inf);
		int c=re(n)-re(m)-re(n-m);
		s[0]=1;
		for(int i=1;i<r;i++){
			s[i]=s[i-1];
			if(i%p) s[i]=s[i]*i%r;
		}
		int ans=qp(p,c,r);
		int d1=ca(n);
		int d2=ca(n-m);
		int d3=ca(m);
		return ans*d1%r*inv(d2,r)%r*inv(d3,r)%r;
	}

可以画图自行理解。

但是，如果你不小心把 ca 函数写成了下面这个东西，你可能仍能 AC 此题，但是这是错误的！

CPP

	int ca(int n){
		if(n==0) return 1;
		return ca(n/p)*qp(s[p-1],n/p,r)%r*s[n%p]%r;
	}

这里给一份 hack：输入 3 1 4，应该输出 3。

如果代码错误的输出 1，原因是：

你的代码可能将

p

当成了一个周期，在计算

3!

时，理论上应该计算

1\times 2\times 3

除掉

2

因子后模

4

的值。但是代码错误的将

p=2

当作周期并错误的认为的

3

和

1

模

4

的值相同，导致得出

1

的结果。

你的exlucas板子可能是假的！

讨论操作

回复

相关推荐

你的exlucas板子可能是假的！