首页 > 代码库 > HDU 5894 hannnnah_j’s Biological Test
HDU 5894 hannnnah_j’s Biological Test
题目链接：传送门
题目大意：有n张板凳围成一圈，有m个人，要让m个人都坐到凳子上且任意两人之间相隔>=k 个凳子，问有多少种方法%（1e9+7）
题目思路：组合数学
我们这样考虑，既然每个人相距>=k 个凳子，m个人就至少有m*k个凳子不能坐人，那我们先从中抽出这m*k个凳子，其它
凳子都可以坐了，然后我们考虑第一个人坐到了一个位置上，剩下的人就有C（n-m*k-1，m-1）种坐法，而第一个人有n种
初始选择，但由于m个人又相同，故应该是C（n-m*k-1，m-1）*n/m种坐法。
Note：一定要注意%MOD，不然中间会爆long long，我就被坑了40min。。。。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <algorithm> 6 #include <cstring> 7 #include <stack> 8 #include <cctype> 9 #include <queue>10 #include <string>11 #include <vector>12 #include <set>13 #include <map>14 #include <climits>15 #define lson rt<<1,l,mid16 #define rson rt<<1|1,mid+1,r17 #define fi first18 #define se second19 #define ping(x,y) ((x-y)*(x-y))20 #define mst(x,y) memset(x,y,sizeof(x))21 #define mcp(x,y) memcpy(x,y,sizeof(y))22 using namespace std;23 #define gamma 0.577215664901532860606512024 #define MOD 100000000725 #define inf 0x3f3f3f3f26 #define N 100005027 #define maxn 300128 typedef pair<int,int> PII;29 typedef long long LL;30 31 int n,m,k,x,y,v;32 LL fac[N];33 LL ksm(LL a,LL b){34 LL res=1;35 while(b){36 if(b&1)res=res*a%MOD;37 b>>=1;38 a=a*a%MOD;39 }40 return res;41 }42 LL C(LL n,LL m){43 if(m>n||m<0)return 0;44 LL s1=fac[n],s2=fac[n-m]*fac[m]%MOD;45 return s1*ksm(s2,MOD-2)%MOD;46 }47 int main(){48 int i,j,group;49 fac[0]=1ll;for(i=1;i<N;++i)fac[i]=fac[i-1]*i%MOD;50 scanf("%d",&group);51 while(group--){52 scanf("%d%d%d",&n,&m,&k);53 if(m==1){printf("%d\n",n);continue;}54 if(n<m*(k+1)){printf("0\n");continue;}55 printf("%lld\n",1ll*C(n-m*k-1,m-1)*n%MOD*ksm(m,MOD-2)%MOD);56 }57 return 0;58 }
HDU 5894 hannnnah_j’s Biological Test
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。