题解-P1680

本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

题意简述

有 $n$ 个人要分成 $m$ 组，每组至少要 $A_i$ 个人（不用 C 为了防止与下面的排列组合式子冲突），求方案数。

解法

我们发现，人与人之间没有本质区别，那么我们可以把总人数减少 $\sum_{i=1}^n A_i$，预先分配，剩下的人至少要分配到一组一人，因为题目要求大于。

那么对于剩下的人，我们考虑应用隔板法，就是从剩下的 $n-\sum_{i=1}^n A_i$ 个人中使用 $m-1$ 个隔板将其分开，所以答案就是 $C^{m-1}_{n-\sum_{i=1}^n A_i-1}$。

计算排列组合要用逆元。

还有个特例就是如果隔板数量不够输出 $0$。

剩下应该没啥了，直接上代码。

#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;
}