[BZOJ 4710] [Jsoi 2011] 分特产

题目链接

[BZOJ 4710] [Jsoi 2011] 分特产

题解

中档题。题意大概是给定多种不同的物品分给若干个人,每种物品又有一定数量,要求每个人至少拥有一样物品。
首先考虑只分一种物品,且不考虑是否为空,根据隔板法有P(n+m-1,m-1)种方法。
考虑多种物品的话只要把每一种都乘上即可。
接下来考虑没有空余的情况。上述方法算出来的并不能保证每个人均不为空,求出的只有至少0个为空的情况。我们根据同样的方法可以求出至少1个为空,至少2个为空……根据容斥原理,至多0个为空的答案为至少0个为空-至少1个为空+至少2个为空-至少3个为空+……

代码

Time:148ms
Memory:1328kB
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 2005;
const int MOD = 1e9 + 7;
long long n, m, ans;
long long  fac[MAXN], inv[MAXN], input[MAXN];

inline long long C(long long a, long long b) {
    return fac[a] * inv[b] % MOD * inv[a - b] % MOD;
};

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    inv[0] = inv[1] = fac[0] = 1;
    for (int i = 2; i < MAXN; i++) {
        inv[i] = inv[MOD%i] * (MOD - MOD / i) % MOD;
    }
    for (int i = 1; i < MAXN; i++) {
        fac[i] = fac[i - 1] * i%MOD;
        inv[i] = inv[i - 1] * inv[i] % MOD;
    }
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> input[i];
    }
    for (int i = 0; i < n; i++) {
        long long temp = C(n, i);
        for (int j = 1; j <= m; j++) {
            temp = temp * C(input[j] + n - i - 1, n - i - 1) % MOD;
        }
        ans += (i & 1) ? MOD - temp : temp;
        ans %= MOD;
    }
    cout << ans << endl;
}

标签: combinatorics

添加新评论