CF451E Devu and Flowers

LuoGu: CF451E Devu and Flowers

CF: E. Devu and Flowers

容斥原理的一般形式：

$$
f(S)=\sum_{T\subseteq S}g(T)
$$

那么就有

$$
g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T)
$$

或者有补集的形式：

$$
f(S)=\sum_{S\subseteq T}g(T)
$$

那么

$$
g(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}f(T)
$$

先不考虑每个数的限制，$n$ 种物品种选择 $m$ 个，每种物品没有限制，那么有 $\binom {n - 1}{n + m - 1}$ 种方案。考虑隔板法，如果每种至少选择一个，答案为 $\binom {n - 1}{m - 1}$ ，现在没有要求至少选择一个，那么相当于多了 $n$ 个物品，然后至少选择一个，即 $\binom {n + m - 1} {n - 1}$ 。

现在有了限制，考虑容斥，选择一个集合其中都超过了限制，那么将还剩的数继续分给其他的数。记 $f _ S$ 表示集合内的所有元素钦定超过限制的情况的答案，$g _ S$ 表示集合内的所有元素都恰好超过限制的情况的答案，那么有 $ f _ S = \binom {n + m - 1 - (\sum _ {i \in S} n _ i + 1)} {m - 1}$ ，并且有 $f _ S = \sum _ {T \subseteq S} g _ S$ ，由容斥原理的一般形式，有 $g(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}f(T)$ ，那么答案 $g(0) = \sum _ {T} (-1) ^ {|T|} f(T)$ 。

查看代码

#include <cstdio>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
typedef long long LL;
const int N = 30, mod = 1e9 + 7;
void adj (int &x)
{
    x += x >> 31 & mod;
}
LL m, w[N];
int n, inv[N];
void init ()
{
    inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = (LL)(mod - mod / i) * inv[mod % i] % mod;
}
int C (LL a, int b)
{
    if (a < 0 || b < 0 || a < b) return 0;
    a %= mod;
    if (!a || !b) return 1;
    int res = 1;
    for (int i = 0; i < b; ++i)
        res = (LL)res * (a - i) % mod;
    for (int i = 1; i <= b; ++i)
        res = (LL)res * inv[i] % mod;
    return res;
}
int main ()
{
    read(n, m);
    init();
    for (int i = 1; i <= n; ++i) read(w[i]);
    int res = 0;
    for (int i = 0; i < 1 << n; ++i)
    {
        LL t = n + m - 1;
        int p = 0;
        for (int j = 0; j < n; ++j)
            if (i >> j & 1) ++p, t -= w[j + 1] + 1;
        p & 1 ? adj(res -= C(t, n - 1)) : adj(res += C(t, n - 1) - mod);
    }
    write(res);
    return 0;
}