奖品分配

思路与分析

题目关键限制条件是：$N \le \sum a_i \le N + 1$。这意味着所有奖品刚好分完，或者恰好剩下 0 个 或 1 个 奖品。

情况一：奖品刚好分完

如果奖品总数刚好等于学生人数 $N$，说明每种奖品必须全部发完（第 $i$ 种奖品正好发掉 $a_i$ 个）。

• 这个问题等价于求多重集的全排列。

• 方案数直接用多重组合数计算：

  $\frac{N!}{a_0! \cdot a_1! \cdot \dots \cdot a_{M-1}!}$

情况二：多出了 1 个奖品

如果有 $N+1$ 个奖品，说明分配完 $N$ 名学生后，会剩下 1 个奖品。

• 转换思路：与其考虑怎么分 $N$ 个奖品给 $N$ 个人，不如考虑是哪一种奖品被剩下了。

• 假设剩下的奖品种类是第 $k$ 种（条件要求 $a_k \ge 1$），那么实际上发出去的第 $k$ 种奖品数量就变成了 $a_k - 1$ 个。

• 此时发出去的奖品总数正好是 $N$ 个，对应发给学生的方案数为：

  $\frac{N!}{a_0! \cdot \dots \cdot (a_k - 1)! \cdot \dots \cdot a_{M-1}!}$

• 我们遍历所有可能的 $k$（只要 $a_k > 0$），将所有情况的方案数相加即可：

  $\text{总方案数} = \sum_{k=0, a_k > 0}^{M-1} \frac{N!}{a_0! \cdots (a_k - 1)! \cdots a_{M-1}!}$

公式化简技巧

在情况二中，如果对每个 $k$ 都单独计算一次多重组合数，时间复杂度会极高。我们可以对式子进行化简：

注意到：

$\frac{N!}{a_0! \cdots (a_k - 1)! \cdots a_{M-1}!} = \frac{N!}{\prod a_i!} \times a_k$

将这个形式代入求和公式中，提公因式得到：

$\text{总方案数} = \frac{N!}{\prod_{i=0}^{M-1} a_i!} \times \sum_{k=0}^{M-1} a_k$

因为已知 $\sum a_i = N + 1$，代入上式化简为：

$\text{总方案数} = \frac{N!}{\prod_{i=0}^{M-1} a_i!} \times (N + 1) = \frac{(N + 1)!}{\prod_{i=0}^{M-1} a_i!}$

也就是说：

• 若 $\sum a_i = N$：答案为 $\frac{N!}{\prod a_i!}$
• 若 $\sum a_i = N + 1$：答案直接为 $\frac{(N + 1)!}{\prod a_i!}$

算法步骤

1. 预处理阶乘与逆元：
   • 题目中 $N \le 1000$，数据范围较小。
   • 预处理出 $0$ 到 $N+1$ 的阶乘 fact[i]，以及对应的模 $10^9 + 7$ 意义下的乘法逆元 invFact[i]（可用费马小定理 + 快速幂求解）。
2. 处理每组询问：
   • 计算当前班级所有 $a_i$ 的和 $S = \sum a_i$。
   • 分母部分 $D = \prod_{i=0}^{M-1} (a_i! \bmod (10^9+7))$。
   • 若 $S = N$：输出 $\text{fact}[N] \times D^{-1} \bmod (10^9+7)$。
   • 若 $S = N + 1$：输出 $\text{fact}[N+1] \times D^{-1} \bmod (10^9+7)$。

单次询问时间复杂度为 $O(M)$，整体复杂度为 $O(\max(N) + T \cdot M)$，可在 $1.00\text{s}$ 的限制内高效通过。

参考代码

#include <iostream>
#include <vector>

using namespace std;

static const int MOD = 1000000007;
static const int MAXN = 2005;

// 阶乘与逆元数组
long long fact[MAXN];
long long invFact[MAXN];

// 快速幂计算 (a^b % MOD)
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 费马小定理求乘法逆元
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

// 预处理阶乘和阶乘逆元
void precompute() {
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
        invFact[i] = modInverse(fact[i]);
    }
}

void solve() {
    int n, m;
    if (!(cin >> n >> m)) return;

    long long sum_a = 0;
    long long denominator_inv = 1; // 用于累乘 1 / (a_i!)

    for (int i = 0; i < m; i++) {
        long long a;
        cin >> a;
        sum_a += a;
        denominator_inv = (denominator_inv * invFact[a]) % MOD;
    }

    // 根据总数分类讨论并使用化简公式
    if (sum_a == n) {
        long long ans = (fact[n] * denominator_inv) % MOD;
        cout << ans << "\n";
    } else if (sum_a == n + 1) {
        long long ans = (fact[n + 1] * denominator_inv) % MOD;
        cout << ans << "\n";
    }
}

int main() {
    // 优化标准输入输出流加速
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    precompute();

    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }

    return 0;
}