GESP2023年12月认证C++八级( 第三部分编程题（1）奖品分配）

参考程序：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;const int N = 1005; // 定义最大可能的N值
const int mod = 1e9 + 7; // 定义模数int C[N + 5][N + 5]; // 组合数数组，C[n][k]表示从n个中选k个的组合数
int a[N + 5]; // 存储每种奖品的数量// 辅助函数，实现模加法
void add(int &a, int b) {a += b;if (a >= mod) a -= mod;
}// 预处理组合数表
void init() {C[0][0] = 1; // 初始化C(0,0)=1for (int i = 1; i <= N; i++) {C[i][0] = C[i][i] = 1; // 初始化C(i,0)=C(i,i)=1for (int j = 1; j < i; j++) {C[i][j] = C[i - 1][j - 1]; // 递推公式：C(i,j)=C(i-1,j-1)+C(i-1,j)add(C[i][j], C[i - 1][j]);}}
}int main() {init(); // 预处理组合数int T;scanf("%d", &T); // 读取班级数量while (T--) {int n, m, sum = 0;scanf("%d%d", &n, &m); // 读取同学数量n和奖品种类mfor (int i = 1; i <= m; i++) {scanf("%d", &a[i]); // 读取每种奖品的数量sum += a[i]; // 计算奖品总数}int ans = 1;if (sum == n) {// 奖品总数等于n，直接计算多重排列for (int i = 1; i <= m; i++) {ans = 1ll * ans * C[n][a[i]] % mod; // 乘组合数C(n,a_i)n -= a[i]; // 更新剩余的n}} else if (sum == n + 1) {// 奖品总数等于n+1，需要去掉一个多余的奖品ans = 0;for (int k = 1; k <= m; k++) {if (a[k] >= 1) {int temp = 1;int remaining = n;for (int i = 1; i <= m; i++) {int cnt = (i == k) ? a[i] - 1 : a[i]; // 第k种奖品去掉一个temp = 1ll * temp * C[remaining][cnt] % mod;remaining -= cnt;}add(ans, temp); // 累加所有可能的方案}}}cout << ans << endl; // 输出结果}return 0;
}