排列组合+组合数取模 HDU 5894

74 阅读 0 评论 49 点赞

我是靠谱客的博主文静日记本，最近开发中收集的这篇文章主要介绍排列组合+组合数取模 HDU 5894，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

 1 // 排列组合+组合数取模 HDU 5894
 2 // 题意：n个座位不同，m个人去坐(人是一样的)，每个人之间至少相隔k个座位问方案数
 3 // 思路：
 4 // 定好m个人 相邻人之间k个座位 剩下就剩n-(m+1)*k个座位
 5 // 剩下座位去插m个不同的盒子==就等价n个相同的球放m个不同的盒子
 6 // 然后组合数出来了
 7 // 乘n的话是枚举座位，除m是去掉枚举第一个座位的时候，剩下人相邻的座位相对不变的情况
 8
 9 #include <iostream>
10 #include <algorithm>
11 #include <cstring>
12 #include <cstdio>
13 #include <vector>
14 #include <cmath>
15 #include <map>
16 #include <queue>
17 using namespace std;
18 #define LL long long
19 typedef pair<int,int> pii;
20 const int inf = 0x3f3f3f3f;
21 const int mod = 1e9+7;
22 const int N = 1e6+10;
23 const int maxx = 200010;
24 #define clc(a,b) memset(a,b,sizeof(a))
25 const double eps = 1e-8;
26 void fre() {freopen("in.txt","r",stdin);}
27 void freout() {freopen("out.txt","w",stdout);}
28 inline int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;}
29
30 int f[N];
31 int inv(int x){
32
int ret=1,y=mod-2;
33
while(y){
34
if(y&1)ret=1ll*ret*x%mod;
35
y>>=1;x=1ll*x*x%mod;
36 
}
37
return ret;
38 }
39 int C(int n,int m){
40
if(n<m)return 0;
41
int ret=1ll*f[n]*inv(f[m])%mod;
42
ret=1ll*ret*inv(f[n-m])%mod;
43
return ret;
44 }
45 int lucas(int n,int m){
46
if(m == 0) return 1;
47
return 1ll*C(n % mod, m % mod) * lucas(n / mod, m / mod) % mod;
48 }
49
50 void init(){
51
f[0]=1;
52
for(int i=1;i<=N-5;++i)f[i]=1ll*i*f[i-1]%mod;
53 }
54
55 int main(){
56 
init();
57
int T;
58
scanf("%d",&T);
59
while(T--){
60
int n,m,k;
61
scanf("%d%d%d",&n,&m,&k);
62
if(m==1){
63
printf("%dn",n);
64
continue;
65 
}
66
LL res=n-(m+1)*k;
67
if(res<0){
68
printf("0n");
69
continue;
70 
}
71
LL tem=lucas(n-m*k-1,m-1);
72
LL ans=((tem)%mod)*n%mod;
73
printf("%dn",(ans*inv(m))%mod);
74 
}
75
return 0;
76 }