hdu 5894 hannnnah_j’s Biological Test 组合数学

时间:2022-08-13 14:33:07

传送门:hdu 5894 hannnnah_j’s Biological Test

题目大意:n个座位,m个学生,使每个学生的间隔至少为k个座位

组合中的插空法

思路:每个学生先去掉k个空位间隔,剩下n-k*m;这些空位至少要坐m个学生,n-k*m-1个空,插m-1个门,方法数为:c(n-k*m-1,m-1);当只有一个学生时,间隔K个位的条件就没必要了,也就是n>k+1的条件不一定要成立

顺带弄了个Lucas的模板

/**************************************************************
Problem:hdu 5894 hannnnah_j’s Biological Test
User: youmi
Language: C++
Result: Accepted
Time:436MS
Memory:17240K
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#define zeros(a) memset(a,0,sizeof(a))
#define ones(a) memset(a,-1,sizeof(a))
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scs(a) scanf("%s",a)
#define sclld(a) scanf("%I64d",&a)
#define pt(a) printf("%d\n",a)
#define ptlld(a) printf("%I64d\n",a)
#define rep(i,from,to) for(int i=from;i<=to;i++)
#define irep(i,to,from) for(int i=to;i>=from;i--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define lson (step<<1)
#define rson (lson+1)
#define eps 1e-6
#define oo 0x3fffffff
#define TEST cout<<"*************************"<<endl
const double pi=*atan(1.0); using namespace std;
typedef long long ll;
template <class T> inline void read(T &n)
{
char c; int flag = ;
for (c = getchar(); !(c >= '' && c <= '' || c == '-'); c = getchar()); if (c == '-') flag = -, n = ; else n = c - '';
for (c = getchar(); c >= '' && c <= ''; c = getchar()) n = n * + c - ''; n *= flag;
}
ll Pow(ll base, ll n, ll mo)
{
ll res=;
while(n)
{
if(n&)
res=res*base%mo;
n>>=;
base=base*base%mo;
}
return res;
}
//*************************** ll n,m,k;
const int maxn=+;
const ll mod=;
ll fac[maxn],inver[maxn];
ll inv(ll aa)
{
return Pow(aa,mod-,mod);
}
void init()
{
fac[]=,fac[]=;
inver[]=,inver[]=;
rep(i,,maxn-)
fac[i]=fac[i-]*i%mod,inver[i]=inver[i-]*inv(i)%mod;
}
ll C(ll aa,ll bb)
{
if(bb>aa)
return ;
ll temp=fac[aa]*inver[bb]%mod*inver[aa-bb]%mod;
return temp;
}
ll lucas(ll aa,ll bb)
{
if(bb==)
return ;
return C(aa%mod,bb%mod)*lucas(aa/mod,bb/mod)%mod;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int T_T;
scanf("%d",&T_T);
init();
for(int kase=;kase<=T_T;kase++)
{
sclld(n),sclld(m),sclld(k);
ll ans=lucas(n-k*m-,m-)*n%mod*inv(m)%mod;
ptlld(ans);
}
}