首页 > 代码库 > HDU5894 hannnnah_j’s Biological Test 组合数取模
HDU5894 hannnnah_j’s Biological Test 组合数取模
http://acm.hdu.edu.cn/showproblem.php?pid=5894
题意：给你n个桌子，m个人，相邻两个人之间相差至少K个桌子。问有多少种坐法。
题解：首先确定第一个人的座位，从n个座位中选择一个，然后确定出符合条件的k*m个座位。最后剩下n-1-k*m个座位，从中选出m-1个座位坐人。总数sum=n*C(n-1-k*m,m-1);
由于有m个重合，因此要sum=sum/m;例如：（2，4，7），（4，7，2），（7，2，4）是一样的。
计算组合数和sum/m时可以使用乘法逆元：(a/b)%mod=a*(b^(mod-2)) mod为素数。
可以参考：http://www.2cto.com/kf/201508/433007.html
也可以用Lucas定理（不明觉厉）；
#include<cstdio>using namespace std;typedef long long ll;const int mod=1e9+7;ll qmod(ll n,ll p) //快速幂取模 { ll result=1; while(p>0) { if(p%2==1) result=(result*n)%mod; p/=2; n=(n*n)%mod; } return result;}ll c(ll n,ll m){ if(n<m) return 0; ll ans=1; for(int i=1;i<=m;i++) ans=ans*((n-m+i)*qmod(i,mod-2)%mod)%mod; //利用乘法逆元 return ans;}main(){ ll t,n,m,k; scanf("%lld",&t); while(t--) { scanf("%lld%lld%lld",&n,&m,&k); if(m==1) printf("%lld\n",n); else printf("%lld\n",(n*c(n-k*m-1,m-1)%mod)*qmod(m,mod-2)%mod); }}
HDU5894 hannnnah_j’s Biological Test 组合数取模
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。