「BZOJ 4710」[JSOI2011]分特产

有 n 个不同的盒子和 m 种球，每种球有 a[i] 个，求将这些球装到这些盒子里且盒子不能 为空的方案数。 \((n,m\le 1000,a[i] \le 1000)\)

Luogu

BZOJ

分析

容斥 + 组合

合法的方案数 = 总的方案数 - 至少 1 个人没有分到的方案数 + 至少 2 个人没有分到的方案数 - ......

考虑至少 i 个人没分到的方案数。分别算每种特产，利用隔板法，则特产 k 的贡献为 \(\binom{a_k+n-i-1}{n-i-1}\) 。最后要随机钦定 i 个人不能分到，即乘上 \(\binom{n}{i}\) 。

于是答案为：

\[\sum\limits_{i=0}^{n-1}\left[(-1)^i\times\binom{n}{i}\prod\limits_{j=1}^{m}\binom{a_j+n-i-1}{n-i-1}\right]\]

代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 2000
#define mod 1000000007
#define DEBUG puts("ok")
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x) {
    T f = 1; x = 0; char c;
    for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x *= f;
}

ll ans;
int n, m;
ll a[N], c[N+1][N+1];

void pre() {
    for (int i = 0; i <= N; ++i) c[i][0] = 1;
    for (int i = 1; i <= N; ++i)
    for (int j = 1; j <= i; ++j)
        c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}

ll solve(int k) {
    ll ret = c[n][k];
    k = n - k - 1;
    for (int i = 1; i <= m; ++i) ret = ret * c[a[i] + k][k] % mod;
    return ret;
}

int main() {
    read(n), read(m);
    pre();
    for (int i = 1; i <= m; ++i) read(a[i]);
    for (int i = 0; i < n; ++i) ans = (ans + (ll)pow(-1, i) * solve(i) + mod) % mod;
    printf("%lld", ans);
    return 0;
}

「BZOJ 4710」[JSOI2011]分特产

原文：https://www.cnblogs.com/hlw1/p/12253303.html