本文章遵守知识共享协议 CC-BY-NC-SA,同步发表于洛谷题解区,转载时须在文章的任一位置附上原文链接和作者署名(rickyxrc)。推荐在我的个人博客阅读。
题意简述
有 个人要分成 组,每组至少要 个人(不用 C 为了防止与下面的排列组合式子冲突),求方案数。
解法
我们发现,人与人之间没有本质区别,那么我们可以把总人数减少 ,预先分配,剩下的人至少要分配到一组一人,因为题目要求大于。
那么对于剩下的人,我们考虑应用隔板法,就是从剩下的 个人中使用 个隔板将其分开,所以答案就是 。
计算排列组合要用逆元。
还有个特例就是如果隔板数量不够输出 。
剩下应该没啥了,直接上代码。
#include<stdio.h>
#define maxn 2000007
#define mod 1000000007
typedef long long i64;
typedef int i32;
i64 fpow(i64 x,int p){
i64 res=1;
while(p){
if(p&1)
res = res * x % mod;
p>>=1;
x = x * x % mod;
}
return res;
}
i64 ginv(i64 x){
return fpow(x,mod-2);
}
i64 jcs[maxn],inv[maxn],n,m,t;
i64 C(i64 n,i64 m){
return jcs[n] * inv[m] % mod * inv[n-m] % mod;
}
int main(){
scanf("%lld%lld",&n,&m);
for(i32 i=1;i<=m;i++)
scanf("%lld",&t),
n-=t;
if(m==1)
return printf("1")&0;
jcs[0]=1;
for(i32 i=1;i<maxn;i++)
jcs[i] = jcs[i-1] * i % mod,
inv[i] = ginv(jcs[i]);
printf("%lld",C(n-1,m-1));
return 0;
}