多重集的组合数

原理

见《进阶指南》第175页。

模板题

AcWing-214-Devu和鲜花

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 30, M = 1e9 + 7;
int n, inv[N];
LL a[N], m;

int power (int a, int b, int p) {
    int res = 1 % p;
    while (b > 0) {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b /= 2;
    }
    return res;
}
int C (LL n, int m) {
    if (n < 0 || m < 0 || n < m) return 0;
    n = n % M; // Lucas 定理
    if (n == 0 || m == 0) return 1;
    int res = 1;
    for (int i = 0; i < m; ++ i)
        res = res * (n - i) % M;
    for (int i = 1; i <= m; ++ i)
        res = (LL)res * inv[i] % M;
    return res;
}

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    for (int i = 1; i <= 20; ++ i) inv[i] = power(i, M - 2, M);
    LL res = 0;
    for (int x = 0; x < (1 << n); ++ x) { // 容斥
        if (x == 0) {
            res = (res + C(n + m - 1, n - 1)) % M;
        } else {
            LL t = n + m;
            int cnt = 0;
            for (int i = 0; i < n; ++ i) {
                if ((x >> i) & 1) {
                    t -= a[i + 1];
                    ++ cnt;
                }
            }
            t -= cnt + 1;
            if (cnt & 1)
                res = (res - C(t, n - 1)) % M;
            else
                res = (res + C(t, n - 1)) % M;
        }
    }
    cout << (res % M + M) % M << endl;
    return 0;
}