XDU1199题解

题意

从n个皮卡丘里选出m个放到圆盘上旋转，问共有多少种选择方式，结果对p取模。

笺释

一开始觉得应该与组合数取模那些有关系，实际上并没有。
从n个里选出m就是n！/（n-m）！
但是注意要去掉旋转序相同的一部分，也就是除以m。
一开始以为去掉逆序的部分就可以了，那样的话就是除以2
得到公式n！/(（n-m）！*m)%p
然后处理一下超精度问题即可，我们知道，如果是单纯的乘法的话可以把取模放到过程中进行避免超精度。
也就是说(a*b*c*d)%p=(a%p)(b%p)(c%p)*(d%p)
在这个题目中，尽管存在着除法的部分，但是除法的部分可以用分子乘法部分消去
用n！消去(n-m)!很好考虑，剩下的是(n-m+1)(n-m+2)…(n-m+m)
然后考虑消去m，m是一定可以与(n-m+1)(n-m+2)…(n-m+m)中的一项约分的，要不然的话最终方法数一定不是整数。
所以让m与能与之约分的第一项约分掉就可以了。

完整代码

#include using namespace std; int n,m,p; int main() { while(~scanf("%d %d %d",&n,&m,&p)) { long long ans=1,flag=0; for(int i=1;i<=m;i++) { int tem=n-m+i; if(tem%m==0&&flag==0) { tem/=m; flag=1; } ans*=tem%p; ans%=p; } printf("%lld ",ans); } }