CF451E Devu and Flowers 多重集组合数

题意：多重集的组合数模板题。
solution：
首先考虑任意$ f_i≥s$的情况，考虑插板法，那么原命题可以等价于求n-1个板子和s朵花组成的排列数：

即多重集{\({ (n-1)·1,s·0 }\)}的全排列数:\(P=\frac{(n+s-1)!}{(n-1)!*s!}=C_{n+s-1}^{n-1}=C_{n+s-1}^{s}\) 。

那么再考虑存在$ f_i<s$的情况。

这个时候会出现一个问题，那就是有可能在划分的时候出现了一个花瓶分到的数量比它本身有的多。

所以考虑容斥一下。

可以钦定对于每一个i，先取走\(f_i+1\)个，然后在剩下的n+s-fi-2个中取s-fi-1个即可，方案数：\(C_{n+s-fi-2}^{n-1}\)

上面的方案数实际上为第i个花瓶至少取了\(f_i+1\)个的方案数，不妨记为\(S_i\) 。

那么答案应该为：
\[ ans=C_{n+s-1}^{n-1}-(\sum{S_i}-\sum{S_i∪S_j}+…+(-1)^{n-1}·({S_1∪…∪S_n})) \]
code：

#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define IL inline
#define LL long long
#define DB double
using namespace std;

IL LL gi() {
   RG LL x=0,w=0; char ch=getchar();
   while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();}
   while (ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
   return w?-x:x;
}

const int N=21;
const int mod=1e9+7;

LL s,f[N];
int n,inv[N];

IL int qpow(int x,int p) {
    RG int ans=1;
    for(;p;p>>=1,x=1ll*x*x%mod)
        if(p&1) ans=1ll*ans*x%mod;
    return ans;
}

IL int C(LL a,int b) {
    if(a<b) return 0;
    if(a>mod) a%=mod;
    if(a==0||b==0) return 1;
    RG int i,ans=1;
    for(i=0;i<b;++i) ans=1ll*ans*(a-i)%mod;
    for(i=1;i<=b;++i) ans=1ll*ans*inv[i]%mod;
    return ans;
}

signed main()
{
    RG LL k;
    RG int i,j,cnt,ans=0;
    n=gi(),s=gi();
    for(i=1;i<=n;++i) f[i]=gi();
    for(i=1;i<=n;++i) inv[i]=qpow(i,mod-2);
    ans=C((LL)n+s-1,n-1);
    for(i=1;i<1<<n;++i) {
        k=n+s-1,cnt=0;
        for(j=0;j<n;++j)
            if(i&(1<<j)) ++cnt,k-=f[j+1]+1;
        if(cnt&1) ans=(ans-C(k,n-1)+mod)%mod;
        else ans=((LL)ans+C(k,n-1))%mod;
    }
    printf("%d\n",ans);
    return 0;
}
// CF451E Devu and Flowers
// 多重集的排列数

CF451E Devu and Flowers 多重集组合数

原文：https://www.cnblogs.com/Bhllx/p/10848685.html