A20227. 作品选拔
填空题
困难
知识点
题目描述
作品选拔
题目描述
创新大赛组委会收到了 n 件学生参赛作品，每件作品都有对应的综合评审得分，其中第 i 件作品的得分为 ai。
根据赛事章程，组委会需从所有备选作品中选出 m 件作品晋级市级终评。为保障终评作品的整体质量，要求选出的 m 件作品中，至少有 k 件作品的综合得分不低于赛事划定的基准线 x。
请你帮助组委会计算，一共有多少种符合要求的作品遴选方案？由于答案数值可能过大，请输出方案数对998244353取模后的结果。
输入格式
第一行，两个正整数n、m；
第二行，n 个正整数，分别表示 a1、a2、……、an；
第三行，两个正整数 k、x。
输出格式
输出满足条件的方案数对 998244353 取模后的结果。
输入样例#1
3 2
10 20 30
1 20输出样例#1
3输入样例#2
4 2
5 10 15 20
1 12输出样例#2
5说明提示
对于50%的数据，1≤n≤20；
对于100%的数据，1≤n≤1000，1≤k≤m≤n，1≤ai、x≤10^9。
限制
时间限制：1000ms，内存限制：256MiB
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
const int MOD = 998244353;
const int MAX = 1005;
long long C[MAX][MAX];
// 预处理组合数 C(n, k)
void init() {
C[0][0] = 1;
for (int i = 1; i < MAX; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
}
int main() {
init();
// 第一步：读 n, m
int n, m;
cin >> n >> m;
// 第二步：读 n 个分数
int a[MAX];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 第三步：读 k, x
int k, x;
cin >> k >> x;
// 统计高分、低分数量
int high = 0, low = 0;
for (int i = 0; i < n; i++) {
if (a[i] >= x) high++;
else low++;
}
// 计算答案
long long ans = 0;
int max_t = min(high, m);
for (int t = k; t <= max_t; t++) {
int need = m - t;
if (need < 0 || need > low) continue;
ans = (ans + C[high][t] * C[low][need]) % MOD;
}
cout << ans << endl;
return 0;
}
上一题
下一题