\(\mathcal Preface\)
可能容斥原理的公式等还是 \(AK\ IOI\) 的巨佬讲得详细，大家可以看看这篇博客。
这篇博客把我写得手废了。
我这个里这接上公式：
\[|\bigcup\limits_{i=1}^{N}S_i|=\sum\limits_{i=1}^{N}|S_i| - \sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}|S_i \bigcap S_j|+\sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}\sum\limits_{k=j+1}^{N}|S_i\bigcap S_j\bigcap S_k|\cdots \]例题
先在这里明确一下（与题目翻译有所不同）：\(n\) 表示花瓶的个数，\(m\) 表示需要的花的数量，\(f_i\) 表示第 \(i\) 个花瓶花的朵数。
【题目大意】
让我们求出序列 \(q\) 的个数。
其中序列 \(q\) 要满足以下条件：
- \(\left(\sum\limits_{i=1}^{n}q_i\right) = m\)。
- \(q_i \le f_i\)
【分析】
如果我们去除条件 \(2\)，则让我们求 \(\left(\sum\limits_{i=1}^{n}q_i\right) = m\) 的非负整数解的个数。
首先我们把 \(y_i = q_i + 1\)，则我们要求出 \(\left(\sum\limits_{i=1}^{n}y_i\right) = n + m\) 的正整数解的个数。
即求不定方程正整数解的个数，这个可以用隔板法做。
形象化的说：
\(\underbrace{1\ 1\cdots1\ 1\ 1}_{n+m\text{ 个 }1}\) 中放入 \(n - 1\) 个隔板（至于为什么是 \(n-1\) 个隔板，我都不知道该怎么讲，可以滚回小学去了）。
那么我们要从 \(n+m-1\) 个空隙中（至于为什么是 \(n+m-1\) 个空隙，我依旧不知道怎么讲）选出 \(n-1\) 个空隙放隔板，那么这个就是小学奥数题，即为 \(\dbinom{n+m-1}{n-1}\)（这玩意就等于 \(C_{n+m-1}^{n-1}\)）。
然后加上条件 \(2\)，对于一个不合法的解至少有一个 \(1\le i\le n\) 满足 \(q_i > f_i\)。
我们把 \(q_i > f_i\) 的 \(q_i\) 表示成一个集合 \(S_i\)。
则不合法的解为一开始的公式（我只不过复制了一下）：
则答案就为：
\[\dbinom{n+m-1}{n-1}-|\bigcup\limits_{i=1}^{N}S_i|=\dbinom{n+m-1}{n-1}-\sum\limits_{i=1}^{N}|S_i| + \sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}|S_i \bigcap S_j|-\sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}\sum\limits_{k=j+1}^{N}|S_i\bigcap S_j\bigcap S_k|\cdots \]然后问题又来了，如果求上面的答案呢。
我们发现如果 \(S_i\) 不合法必定是 \(q_i > f_i\) 这个就为 \(q_i \ge f_i+1\)，那么我们把 \(q_i\) 减去 \(f_i+1\)。
那么不管你剩余的 \(m - (f_i + 1)\) 个花怎么选都是 \(\in S_i\) 的。
这里是没有 \(f_i\) 进行限制，那么这用回到了之前求不定方程解的个数。
答案就为 \(\dbinom{n+m-f_i-2}{n-1}\)（这玩意就为 \(C_{n+m-f_i-2}^{n-1}\)），如果看到这里模糊的话请仔细阅读起那面求不定方程的过程。
那么如果是 \(|S_i \bigcap S_j|\) 也是同理。
要同时满足 \(q_i > f_i\) 和 \(q_j > f_j\)，那么和上面一样减去 \(q_i + 1\) 和 \(q_j + 1\)。
然后再从剩余的 \(m - (q_i + 1) - (q_j + 1)\) 朵花中去选。
答案为 \(\dbinom{n+m-f_i-f_j-3}{n-1}\)（这玩意就为 \(C_{n+m-f_i-f_j-3}^{n-1}\)）。
然后我们把答案再写一下：
\[\dbinom{n+m-1}{n-1}-|\bigcup\limits_{i=1}^{N}S_i|=\dbinom{n+m-1}{n-1}-\sum\limits_{i=1}^{N}\dbinom{n+m-f_i-2}{n-1}+\sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}\dbinom{n+m-f_i-f_j-3}{n-1}-\sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^{N}\sum\limits_{k=j+1}^{N}\dbinom{n+m-f_i-f_j-f_k-4}{n-1}\cdots \]这个组合数的求法就按照 \(C_{b}^{a}=\frac{b\times(b-1)\times\cdots (b-a+1)}{a!}\)，因为 \(a \le 20\)，与 \(n\) 同级，所以时间复杂度为 \(\mathcal O(n)\)。
然后那个柿子可以用二进制枚举来求，如果二进制中第 \(i\) 位是 \(1\) 表示要属于集合 \(S_i\)。
时间复杂度：\(\mathcal O(2^n\times n)\)，空间复杂度：\(\mathcal O(n)\)。
\(\mathcal Code\)
#include <bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false)
#define cit cin.tie(0)
#define cot cout.tie(0)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 20, M = 100010, MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
void solve();
int main()
{
IOS;
cit, cot;
int T = 1;
// cin >> T;
while (T -- ) solve();
return 0;
}
LL n, m;
LL q[N];
int qmi(int a, int k)
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % MOD;
a = (LL)a * a % MOD;
k >>= 1;
}
return res;
}
int C(LL a, LL b)
{
if (a < b) return 0;
int x = 1, y = 1;
for (LL i = a - b + 1; i <= a; i ++ ) x = i % MOD * x % MOD;
for (int i = 1; i <= b; i ++ ) y = y * (LL)i % MOD;
return x * (LL)qmi(y, MOD - 2) % MOD;
}
void solve()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> q[i];
int res = 0;
for (int i = 0; i < 1 << n; i ++ )
{
LL a = m + n - 1, b = n - 1;
int sign = 1;
for (int j = 0; j < n; j ++ )
if (i >> j & 1)
{
sign *= -1;
a -= q[j] + 1;
}
res = ((res + C(a, b) * sign) % MOD + MOD) % MOD;
}
cout << res << endl;
}