만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

고전적인 개수 세기 문제

시간 제한2초메모리 제한1024 MB

요약
각 심사위원이 v개 문제에 투표한 뒤 상위 p개가 될 수 있는 문제 집합의 개수를 998244353으로 나눈 나머지로 구합니다.
난이도

어려움10점 중 8점

유형
동적 계획법, 조합론, 정렬
정답자
아직 제출이 없습니다

문제

이번 대회를 위해 nn개의 문제가 제안되었다. ii번 문제의 초기 점수는 정수 aia_i점이다.

mm명의 심사위원이 마음에 드는 문제에 투표한다. 각 심사위원은 다른 심사위원과 독립적으로 정확히 vv개의 문제를 고르고, 고른 문제마다 점수를 11씩 올린다.

mm명의 심사위원이 모두 투표를 마치면 문제를 점수의 내림차순으로 정렬하고, 앞의 pp개 문제를 문제집에 넣는다. 여기서 pp는 11 이상 nn 이하의 어떤 값이든 될 수 있다. 점수가 같은 문제의 순서는 임의로 정할 수 있으며, 이 순서는 대회 감독이 정한다.

가능한 문제집은 몇 가지인가? 이 수를 998 244 353998\,244\,353으로 나눈 나머지를 출력하라. 한쪽 문제집에만 속한 문제가 하나라도 있으면 두 문제집은 서로 다른 것으로 본다.

입력

각 테스트 케이스는 여러 개의 테스트 케이스로 구성된다. 첫 줄에 테스트 케이스의 개수 tt (1≤t≤501 \le t \le 50)가 주어진다. 각 테스트 케이스의 설명이 이어진다.

각 테스트 케이스의 첫 줄에는 문제의 개수 nn, 심사위원의 수 mm, 각 심사위원이 고르는 문제의 수 vv가 주어진다 (2≤n≤1002 \le n \le 100; 1≤m≤1001 \le m \le 100; 1≤v≤n−11 \le v \le n - 1).

둘째 줄에는 문제들의 초기 점수 a1,a2,…,ana_1, a_2, \ldots, a_n이 주어진다 (0≤ai≤1000 \le a_i \le 100).

모든 테스트 케이스에 대한 nn의 합은 100100을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 문제집의 수를 998 244 353998\,244\,353으로 나눈 나머지를 출력한다.

힌트

첫 번째 테스트 케이스에서 가능한 문제집은 {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\}이다.

세 번째 테스트 케이스에서는 공집합이 아닌 문제들의 부분집합이 모두 가능한 문제집이다.

예제1

  1. 예제 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
    
    예상 출력
    5
    6
    1023
    23
    19
    240