容斥原理

这是前置知识，这里只提一下结论，证明请见OI-Wiki（讲的挺好，看不懂的先弄懂容斥再来吧）。

$\left | \bigcup_{i=1}^nS_i \right |=\sum_{i=1}^n|S_i|-\sum_{1\leq i \leq j \leq n}|S_i\cap S_j|+...+(-1)^{n+1}\left | \bigcap_{i=1}^nS_i \right |$

这里 $S_1,S_2 ... S_n$ 为 $n$ 个有限集合 ， $| S_i |$ 表示 $S_i$ 的大小。

多重组合数

结论

我们先给出结论：
先设集合 $S$

$S=\{n_1*a_1,n_2*a_2,...,n_k*a_k\}$

那么从集合 $S$ 中取 $r$ 个元素的方案数为：

$C_{k-r-1}^{k-1}-\sum_{i=1}^kC_{k+r-n_i-2}^{k-1}+\sum_{1 \leq i\leq j\leq n}C_{k+r-n_i-n_j-3}^{k-1}-...+(-1)^kC_{k+r-\sum_{i=1}^k n_i-(k+1)}^{k-1}$

证明

这篇讲的挺好：

例题

CF451E Devu and Flowers
是一道板子题，可以直接应用容斥原理的结论。
因为范围不大，所以可以直接求组合数。
这里放上 $AC$ 代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9+7;
const int N = 100;
int n,s,a[N],inv[N],ans,i,j;
inline int C(int u, int d)
{
        if ( u>d || u<0 || d<0 ) return 0LL;
        d %= mod;
        long long res=1;
        for (int ii=0; ii<u; ii++)
                res = res * (d-ii) % mod;
        for (int ii=1; ii<=u; ii++)
                res = res * inv[ii] % mod;
        return res;
}//tx
int lucas(int u, int d)
{
        if (u<=mod&&d<=mod) return C(u,d)%mod;
        else return (lucas(u/mod,d/mod))*C(u%mod,d%mod)%mod;//lucus定理计算组合数
}
int ksm(int a, int b)
{
        int res=1;
        while(b)
        {
                if (1&b) res=res*a % mod;
                b>>=1;
                a=a*a%mod;
        }
        return res;
}//ksm
signed main()
{
        cin >> n >> s;
        for (i=1; i<=n; i++) cin >> a[i];
        for (i=1; i<=20; i++)
                inv[i]=ksm(i,mod-2);//这个地方不知道为什么直接写mod会wa
        for (i=0; i< 1<<n; i++)
        {
                int d=n+s,cnt=0;
                for (j=0; j<n; j++)
                        if (i>>j&1)
                                cnt++,d-=a[j+1];
                d-=cnt+1;
                if (1&cnt) ans=(ans-lucas(n-1,d)) % mod;
                else ans = (ans+lucas(n-1,d)) % mod;
        }
        cout << (ans+mod) % mod;
}