HDU 5894 hannnnah_j’s Biological Test (组合数学）

69 阅读 0 评论 46 点赞

我是靠谱客的博主安详玫瑰，最近开发中收集的这篇文章主要介绍HDU 5894 hannnnah_j’s Biological Test (组合数学），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这题没做出来我真想给自己一巴掌。

比赛的时候已经推到了，n-m个座位分成m份，每份不小于k，也就是剩余n-m-m*k个相同的球放到m个不同的盒子里，也知道n个相同的球放到m个不同的盒子里公式是C(n+m-1, m-1);

但是我特么推了半年就是没把这个公式写下来：

C(n - m -m*k + m -1 , m-1) = C(n - m*k -1，m - 1)

说到底还是蠢。

ans = n * C(n - m*k -1，m - 1)/m；

乘n相当于第一个人有n种选择，而学生在这里都是一样的，所以要是重复计算了m次，最后除以m。

【代码】

/* ***********************************************
Author
:angon
************************************************ */
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define showtime fprintf(stderr,"time = %.15fn",clock() / (double)CLOCKS_PER_SEC)
#define lld %I64d
#define REP(i,k,n) for(int i=k;i<n;i++)
#define REPP(i,k,n) for(int i=k;i<=n;i++)
#define scan(d) scanf("%d",&d)
#define scanl(d) scanf("%I64d",&d)
#define scann(n,m) scanf("%d%d",&n,&m)
#define scannl(n,m) scanf("%I64d%I64d",&n,&m)
#define mst(a,k)
memset(a,k,sizeof(a))
#define LL long long
#define N 1000005
#define mod 1000000007
inline int read(){int s=0;char ch=getchar();for(; ch<'0'||ch>'9'; ch=getchar());for(; ch>='0'&&ch<='9'; ch=getchar())s=s*10+ch-'0';return s;}
LL f[N], f2[N], inv[N];
void init()
{
f[0] = f[1] = f2[0] = f2[1] = inv[0] = inv[1] = 1;
for (int i = 2; i < N; i++)
{
f[i] = f[i - 1] * i % mod;
inv[i] = inv[mod % i] * (mod - mod / i) % mod;
f2[i] = f2[i - 1] * inv[i] % mod;
}
}
inline LL C (int n, int m) {
if (m < 0 || n < m) return 0;
return f[n] * f2[m] % mod * f2[n - m] % mod;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
init();
int t;
scan(t);
while(t--)
{
int n,m,k;
scann(n,m);scan(k);
if(m==1)
{
printf("%dn",n);
continue;
}
LL ans = C(n-1-m*k,m-1) * inv[m] % mod * n % mod;
printf("%lldn",ans);
}
return 0;
}