题目链接

题目描述

有 $n$ 个人和 $m$ 种物品，第 $i$ 种物品有 $a_i$ 个，同种物品之间没有区别。

现在要将这些物品分给这些人，使得每个人至少分到一个物品，求方案数模 $10^9 + 7$

$n,m,a_i \le 10^3$

简要做法

每个人至少分到一个物品 $=$ 恰好 $0$ 个人没有分到物品

$f(i)$ 钦定，$g(i)$ 恰好

$$f(k) = \sum_{i=k}^{n}{i\choose k}g(i) = {n\choose k}\prod_{i=1}^{m}{{n-k+a_i-1}\choose{a_i-1}}$$

$$g(k)=\sum_{i=k}^{n}(-1)^{i-k}{i\choose k}f(i) = \sum_{i=k}^{n}(-1)^{i-k}{i\choose k}{n\choose i}\prod_{j=1}^{m}{{n-i+a_j-1}\choose{a_j-1}}$$

$$ans = g(0) = \sum_{i=0}^{n}(-1)^{i}{n\choose i}\prod_{j=1}^{m}{{n-i+a_j-1}\choose{a_j-1}}$$

参考代码

#include <stdio.h>
#include <algorithm>
#include <memory.h>

#define int long long

int read(int x = 0, int f = 0, char ch = getchar())
{
    while ('0' > ch or ch > '9')
        f = ch == '-', ch = getchar();
    while ('0' <= ch and ch <= '9')
        x = x * 10 + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

const int N = 2e3 + 5;
const int P = 1e9 + 7;

int n, m, ans;
int a[N];
int fac[N], inv[N], f[N], g[N];

int pow(int x, int k, int res = 1)
{
    for (x %= P; k; x = x * x % P, k >>= 1)
        if (k & 1)
            res = res * x % P;
    return res;
}

int C(int i, int j) { return fac[i] * inv[j] % P * inv[i - j] % P; }

signed main()
{
    n = read(), m = read();
    for (int i = 1; i <= m; i++)
        a[i] = read();
    fac[0] = 1;
    for (int i = 1; i < N; i++)
        fac[i] = fac[i - 1] * i % P;
    inv[N - 1] = pow(fac[N - 1], P - 2);
    for (int i = N - 1; i >= 1; i--)
        inv[i - 1] = inv[i] * i % P;
    for (int i = 0; i < n; i++)
    {
        int x = C(n, i);
        for (int j = 1; j <= m; j++)
            (x *= C(n - i + a[j] - 1, a[j])) %= P;
        if (i & 1)
            ans = (ans - x + P) % P;
        else
            ans = (ans + x) % P;
    }
    return printf("%lld", ans), 0;
}