「JSOI2011」分特产

「JSOI2011」分特产

传送门

计数题。

考虑容斥掉每人至少一个的限制。

就直接枚举至少有多少人没有分到特产，然后剩下的随便分。

\[Ans = \sum_{i = 0}^n (-1)^i {n \choose i} \prod_{j = 1}^m {n - i + a_j - 1 \choose n - i - 1}
\]

参考代码：

#include <cstdio>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

template < class T > inline void read(T& s) {

    s = 0; int f = 0; char c = getchar();

    while ('0' > c || c > '9') f |= c == '-', c = getchar();

    while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

    s = f ? -s : s;

}

const int _ = 5010, p = 1e9 + 7;

int n, m, a[_], fac[_], ifc[_];

inline int C(int N, int M) { return 1ll * fac[N] * ifc[M] % p * ifc[N - M] % p; }

inline void init(int N) {

    fac[0] = ifc[0] = ifc[1] = 1;

    for (rg int i = 1; i <= N; ++i) fac[i] = 1ll * fac[i - 1] * i % p;

    for (rg int i = 2; i <= N; ++i) ifc[i] = 1ll * (p - p / i) * ifc[p % i] % p;

    for (rg int i = 1; i <= N; ++i) ifc[i] = 1ll * ifc[i - 1] * ifc[i] % p;

}

int main() {

#ifndef ONLINE_JUDGE

    file("cpp");

#endif

    read(n), read(m), init(_ - 1);

    for (rg int i = 1; i <= m; ++i) read(a[i]);

    int ans = 0;

    for (rg int i = 0; i <= n; ++i) {

	    int tmp = 1;

	    for (rg int j = 1; j <= m; ++j) tmp = 1ll * tmp * C(n - i - 1 + a[j], n - i - 1) % p;

	    ans = (ans + 1ll * (i & 1 ? -1 : 1) * C(n, i) * tmp % p + p) % p;

    }

    printf("%d\n", ans);

    return 0;

}