首页 > 代码库 > hdu 5894 hannnnah_j’s Biological Test 组合数学

hdu 5894 hannnnah_j’s Biological Test 组合数学

传送门: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<<"*************************"<<endlconst double pi=4*atan(1.0);using namespace std;typedef long long ll;template <class T> inline void read(T &n){    char c; int flag = 1;    for (c = getchar(); !(c >= 0 && c <= 9 || c == -); c = getchar()); if (c == -) flag = -1, n = 0; else n = c - 0;    for (c = getchar(); c >= 0 && c <= 9; c = getchar()) n = n * 10 + c - 0; n *= flag;}ll Pow(ll base, ll n, ll mo){    ll res=1;    while(n)    {        if(n&1)            res=res*base%mo;        n>>=1;        base=base*base%mo;    }    return res;}//***************************ll n,m,k;const int maxn=1000000+10;const ll mod=1000000007;ll fac[maxn],inver[maxn];ll inv(ll aa){    return Pow(aa,mod-2,mod);}void init(){    fac[0]=1,fac[1]=1;    inver[0]=1,inver[1]=1;    rep(i,2,maxn-10)        fac[i]=fac[i-1]*i%mod,inver[i]=inver[i-1]*inv(i)%mod;}ll C(ll aa,ll bb){    if(bb>aa)        return 0;    ll temp=fac[aa]*inver[bb]%mod*inver[aa-bb]%mod;    return temp;}ll lucas(ll aa,ll bb){    if(bb==0)        return 1;    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=1;kase<=T_T;kase++)    {        sclld(n),sclld(m),sclld(k);        ll ans=lucas(n-k*m-1,m-1)*n%mod*inv(m)%mod;        ptlld(ans);    }}

 

hdu 5894 hannnnah_j’s Biological Test 组合数学