首先考虑没有 \(f_i\) 的限制的时候，此时可以用插板法得到方案数为 \(\binom{s + n - 1}{n - 1}\)。
考虑钦定 \(f_i\) 不合法，那么就相当于先在 \(i\) 这里选 \(f_i + 1\)，剩下的随意分配，方案数就为 \(\binom{s - (f_i + 1) + n - 1}{n - 1}\)。
算完过后能发现会算重存在 \(> 1\) 个 \(f_i\) 不合法的情况。
那么就可以用容斥来算。
考虑钦定不合法的下标为 \(p_{1\sim k}\)，方案数即为 \(\binom{s - \sum_{i = 1}^k(f_{p_i} + 1) + n - 1}{n - 1}\)。
容斥系数即为 \((-1)^k\)。
因为 \(n\le 20\)，可以考虑暴力枚举 \(p\) 的所有可能去算。
时间复杂度 \(O(2^nn)\)。
代码
#include<bits/stdc++.h>
using i64 = long long;
const i64 mod = 1e9 + 7;
inline i64 qpow(i64 a, i64 b) {i64 v = 1; while (b) b & 1 && ((v *= a) %= mod), b >>= 1, (a *= a) %= mod; return v;}
const int maxn = 20 + 5;
i64 f[maxn], invf[maxn];
inline i64 C(i64 n, int m) {
i64 tot = invf[m];
while (m--) (tot *= n-- % mod) %= mod;
return tot;
}
int main() {
int n; i64 sum; scanf("%d%lld", &n, &sum);
for (int i = 1; i <= n; i++) scanf("%lld", &f[i]);
invf[0] = 1;
for (int i = 1; i <= n; i++) invf[i] = invf[i - 1] * qpow(i, mod - 2) % mod;
i64 ans = 0;
for (int s = 0; s < (1 << n); s++) {
i64 S = sum;
for (int i = 0; i < n; i++) s >> i & 1 && (S -= f[i + 1] + 1);
if (S < 0) continue;
if (__builtin_popcount(s) & 1) (ans += mod - C(S + n - 1, n - 1)) %= mod;
else (ans += C(S + n - 1, n - 1)) %= mod;
}
printf("%lld\n", ans);
return 0;
}