多重集组合

Posted on 2018-09-01 Views:

无限元素多重集组合

对于一个含有种元素的多重集 $S = \{a_1 \cdot \infty, a_2 \cdot \infty, \cdots, a_k \cdot \infty \}$ ，从当中取出个元素进行组合，共有

$\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个隔板|}$

有限元素多重集组合

对于一个含有种元素共计个的多重集 $S = \{a_1 \cdot n_1, a_2 \cdot n_2, \cdots, a_k \cdot n_k \}$ ，从当中取出个元素进行组合，方案数为：

$\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 表示第种元素选了至少 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;
}