#P18672. Classical Counting Problem

    ID: 18008 传统题 2000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-0/1 背包计数 DP补集计数倒序更新避免重复使用

Classical Counting Problem

Classical Counting Problem

题目描述

为即将举行的一场比赛,一共提出了 nn 道题。第 ii 道题的初始分数为整数 aia_i。

共有 mm 位评委为自己喜欢的题目投票。每位评委独立于其他评委,恰好选择 vv 道不同的题目,并将所选每道题的分数增加 11。不同评委可以选择相同的题目。

全部 mm 位评委投票结束后,将题目按最终分数从高到低排序。对于某个 1≤p≤n1\le p\le n,选取排序后的前 pp 道题作为比赛题集。最终分数相同的题目可以任意排列,具体次序由比赛负责人决定。

在所有可能的投票结果、所有合法的 pp 以及所有允许的同分排列下,一共能得到多少个不同的题集?输出答案对 998244353998244353 取模的结果。如果存在某道题只属于两个题集中的一个,就认为这两个题集不同。题集非空,pp 并未固定为 vv。

输入格式

第一行包含测试用例数 tt(1≤t≤501\le t\le50)。

每个测试用例第一行包含三个整数 n,m,vn,m,v,分别表示题目数、评委数以及每位评委选择的题目数,满足 2≤n≤1002\le n\le100、1≤m≤1001\le m\le100、1≤v≤n−11\le v\le n-1。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n,表示初始分数,满足 0≤ai≤1000\le a_i\le100。

保证所有测试用例的 nn 之和不超过 100100。

输出格式

对每个测试用例输出一行,包含可能题集数对 998244353998244353 取模的结果。

样例输入 1

6
3 1 2
1 2 3
3 2 1
1 2 3
10 1 1
0 0 0 0 0 0 0 0 0 0
6 1 2
2 1 1 3 0 2
6 1 5
2 1 1 3 0 2
10 4 8
7 2 3 6 1 6 5 4 6 5

样例输出 1

5
6
1023
23
19
240

样例说明

第一组测试的全部可能题集为 {2}\{2\}、{3}\{3\}、{1,3}\{1,3\}、{2,3}\{2,3\}、{1,2,3}\{1,2,3\}。

第二组测试的全部可能题集为 {1}\{1\}、{2}\{2\}、{3}\{3\}、{1,3}\{1,3\}、{2,3}\{2,3\}、{1,2,3}\{1,2,3\}。

第三组测试中,任意非空题目子集都可以成为最终题集。