1305: 集训题单
Memory Limit:256 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:10
Solved:1
Description
小爱老师正在准备本次信息学集训的选题,为此他已经准备了 $n$ 道备选试题,每题都有一个难度值,其中第 $i$ 道题的难度值为 $a_i$。
由于集训时长的限制,小爱准备从这些备选试题中选出 $m$ 道试题组成正式的集训题单。为了保证集训的质量及难度,选出的 $m$ 道试题中需保证至少有 $k$ 道试题的难度不低于给定的难度值 $X$。
请你帮助小爱计算一下,一共有多少种不同的选题方式?由于答案可能很大,请输出最终方案数 $\%998244353$ 即可。
(注意:选出相同的试题但前后顺序不同,均认为是同一种选法。)
由于集训时长的限制,小爱准备从这些备选试题中选出 $m$ 道试题组成正式的集训题单。为了保证集训的质量及难度,选出的 $m$ 道试题中需保证至少有 $k$ 道试题的难度不低于给定的难度值 $X$。
请你帮助小爱计算一下,一共有多少种不同的选题方式?由于答案可能很大,请输出最终方案数 $\%998244353$ 即可。
(注意:选出相同的试题但前后顺序不同,均认为是同一种选法。)
Input
输入共三行:
输入第一行,两个正整数 $n,m$
输入第二行,$n$ 个正整数,分别表示 $a_1,a_2,...,a_n$
输入第三行,两个正整数 $k,X$
输入第一行,两个正整数 $n,m$
输入第二行,$n$ 个正整数,分别表示 $a_1,a_2,...,a_n$
输入第三行,两个正整数 $k,X$
Output
输出满足条件的方案数对 $998244353$ 取模后的结果
Sample Input Copy
3 2
10 20 30
1 20
Sample Output Copy
3
HINT
样例1说明:
可以选 $\{10,20\}$,$\{10,30\}$,$\{20,30\}$共 $3$ 种选法
输入样例2:
4 2
5 10 15 20
1 12
输出样例2:
5
样例2说明:
可以选 $\{5,15\},\{5,20\},\{10,15\},\{10,20\},\{15,20\}$ 共 $5$ 种选法
数据范围:
- 对于 $50\%$ 的数据,$1≤n≤20$
- 对于 $100\%$ 的数据,$1≤n≤10^3$ ,$1≤k≤m≤n$ ,$1≤a_i,X≤10^9$
可以选 $\{10,20\}$,$\{10,30\}$,$\{20,30\}$共 $3$ 种选法
输入样例2:
4 2
5 10 15 20
1 12
输出样例2:
5
样例2说明:
可以选 $\{5,15\},\{5,20\},\{10,15\},\{10,20\},\{15,20\}$ 共 $5$ 种选法
数据范围:
- 对于 $50\%$ 的数据,$1≤n≤20$
- 对于 $100\%$ 的数据,$1≤n≤10^3$ ,$1≤k≤m≤n$ ,$1≤a_i,X≤10^9$