zcmimi's blog
avatar
zc
2020-07-25 23:00:00
  • 本文总阅读量
查看原题

点击跳转

n个人和m种物品,第i种物品有a_i个,同种物品之间没有区别。现在要将这些物品分给这些人,使得每个人至少分到一个物品

每个同学都必须至少分得一个

可以通过 恰好没有同学没有分得 来反演

f_i为钦定i个人没有分到,

钦定的方案数为{n\choose i},这时第j种物品分给n-i个人,使用隔板法,方案数为{n-i+a_j-1\choose n-i-1}

f_i={n\choose i}\prod_{j=1}^m{n-i+a_j-1\choose n-i-1}

g_i为恰好i个人没有分到,反演:

g_k=\sum_{i=k}^n(-1)^{i-k}{i \choose k}f_i

那么:

\begin{aligned} ans &=g_0\\ &=\sum_{i=0}^n(-1)^if_i\\ &=\sum_{i=0}^n(-1)^i{n\choose i}\prod_{j=1}^m{n-i+a_j-1\choose n-i-1} \end{aligned}

#include<bits/stdc++.h>
const int N=1001,P=1000000007;
int n,m,a[N],ans,c[N*2][N*2];
void mod(int&x){if(x>=P)x-=P;}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<=2000;++i){
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;++j)
            mod(c[i][j]=c[i-1][j-1]+c[i-1][j]);
    }
    for(int i=1;i<=m;++i)scanf("%d",a+i);
    for(int i=0;i<=n;++i){
        long long res=c[n][i];
        for(int j=1;j<=m;++j)
            (res*=c[n-i+a[j]-1][n-i-1])%=P;
        if(i&1)mod(ans+=P-res);
        else mod(ans+=res);
    }
    printf("%d\n",ans);
}
LG 5505 [JSOI2011]分特产
comment评论
Search
search