1 条题解
-
0
思路
首先考虑奖品总个数=人数的情况，设奖品数分别是,则 总方案数为 ，可以提前预处理排列数C数组的值，方便计算,接着考虑奖品总个数=人数+1的情况，我们可以额外虚设1个人，依然按照奖品总个数=人数的情况计算，并输出方案数，具体的方案为不考虑虚设人拿的奖品种类，把前n个人拿的奖品种类作为方案，考虑为什么这样是对的，对于两种方案，如果虚设人拿的奖品编号相同，那么说明前面n个人拿的奖品编号必然有不同，那么方案是不同的，如果虚设人拿的奖品编号不同，因为总共只有n+1个奖品，所以前面n个人拿的奖品编号必然也不同，方案也是不同的，说明我们在虚设人的情况下得到的任意两个方案都不会重复，所以直接按照人数=奖品总个数计算即可。
参考代码
#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; const int mod = 1e9 + 7; int C[N + 5][N + 5], a[N + 5]; void add(int &a, int b) { a += b; if(a >= mod) a -= mod; } void init() { C[0][0] = 1; for(int i = 1; i <= N; i ++) { C[i][0] = C[i][i] = 1; for(int j = 1; j < i; j ++) C[i][j] = C[i - 1][j - 1], add(C[i][j], C[i - 1][j]); } } int main() { // freopen("data/10.in", "r", stdin); init(); int T; scanf("%d", &T); while(T --) { int n, m, sum = 0; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i ++) scanf("%d", &a[i]), sum += a[i]; int ans = 1; for(int i = 1; i <= m; i ++) { ans = 1ll * ans * C[sum][a[i]] % mod; sum -= a[i]; } cout << ans << endl; } return 0; }
维娜 (RYM)
LV 7
@ 2024-5-30 20:50:47
- 1
