无限元素多重集组合

对于一个含有 \(k\) 种元素的多重集 \(S = \{a_1 \cdot \infty, a_2 \cdot \infty, \cdots, a_k \cdot \infty \}\)，从当中取出 \(r\) 个元素进行组合，共有 \[ \binom{r + k - 1}{k - 1} = \binom{r + k - 1}{r} \]

种取法，这个结论用隔板法易证：

\[ \overbrace {\underbrace {\times \cdots \times \times | \times \times \cdots | \times \times}_{r 个元素 \times}}^{k -1 个隔板 |} \]

有限元素多重集组合

对于一个含有 \(k\) 种元素共计 \(n\) 个的多重集 \(S = \{a_1 \cdot n_1, a_2 \cdot n_2, \cdots, a_k \cdot n_k \}\)，从当中取出 \(r\) 个元素进行组合，方案数为： \[ \sum_{X \subseteq \{1, 2, 3, \cdots, k\}} (-1)^{|X|} \binom{r - \sum_{i \in X}(n_i + 1) + k - 1}{k - 1} \] 证明：

如果没有数量限制那么答案显然是 \(\binom{r + k - 1}{k - 1}\)，但是由于数量有限，我们要排除 \(a_i\) 多于 \(n_i\) 的方案，令 \(P_i\) 表示第 \(i\) 种元素选了至少 \(n_i + 1\) 个的方案集合。要构造这样的方案，我们只需要先选出 \(n_i + 1\) 个该种元素，再在剩下的集合中选出 \(r - n_i - 1\) 个即可，于是我们有 \[ |P_i| = \binom{r - (n_i + 1) + k - 1}{k - 1} \] 所有所有不合法的方案可以表示为

\[ \bigcup_{1 \le i \le k} P_i \] 接下来结合容斥原理易证。

例子：CF451E

就是以上公式的应用，对于容斥原理使用递归的写法，求取组合数时使用了 Lucas 定理加以优化，代码很短：

#include <cstdio>

using namespace std;
typedef long long ll;
const ll P = 1000000007;
const int N = 22;
ll n, m, inv[N], a[N];

ll binom(ll a, ll b) {
    if (a < 0 || b < 0 || a < b) return 0;
    a %= P;
    if (a == 0 || b == 0) return 1;
    ll ret = 1;
    for (ll i = a; i > a - b; i--)
        ret = ret * i % P;
    for (ll i = 1; i <= b; i++)
        ret = ret * inv[i] % P;
    return ret;
}

ll calc(int d, ll x) {
    if (d == 0) return x == 0 ? 0 : binom(n + m - 1 - x, n - 1);
    else return (calc(d - 1, x) - calc(d - 1, x + a[d] + 1)) % P;
}

void setup() {
    inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = (-(P / i) * inv[P % i] % P + P) % P;
}

int main() {
    scanf("%lld%lld", &n, &m);
    setup();
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    ll ans = binom(n + m - 1, n - 1) + calc(n, 0);
    printf("%lld\n", (ans % P + P) % P);
    return 0;
}