QCC P3 - Cohorts

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Due to your superlative performance in online school, you've been employed by CodeVax. Your assignment is as such:

There are N seats in a line. These seats must be divided into exactly Q cohorts to reduce the transmission of the virus. Each cohort consists of a contiguous segment of exactly K seats. An arrangement of cohorts is considered to be valid if there is at least 1 seat between any two cohorts and no cohort overlaps another.

Find the total number of valid arrangements, modulo 998\,244\,353.

Input Specification

The first line will contain the integer T, representing the number of test cases.

The next T lines will each contain the integers N_i, K_i and Q_i for the i^\text{th} test case.

Output Specification

For each test case, output the number of valid arrangements, modulo 998\,244\,353.


1 \le N \le 10^6

1 \le K \le 10^6

1 \le Q \le 5 \times 10^5

1 \le T \le 10^5

Note that you will NOT be required to pass all the samples to receive points.

Subtask 1 [5%]

1 \le T \le 400

1 \le N \le 400

K = 1

Q = 2

Subtask 2 [15%]

1 \le T \le 100

1 \le N \le 100

1 \le Q \le 100

Subtask 3 [80%]

No additional constraints.

Sample Input 1

3 1 1
3 1 2
1 1 2
4 1 2

Sample Output 1


Explanation for Sample 1

Let x represent the spots in the line where the cohorts are and let - represent empty spaces in the line:

For the first test case, the valid cohort arrangements are: x--, -x-, and --x.

For the second test case, the only valid cohort arrangement is: x-x.

For the third test case, there are no valid cohort arrangements.

For the fourth test case, the valid cohort arrangements are: x-x-, x--x, and -x-x.

Sample Input 2

111 22 9
400 25 6

Sample Output 2



There are no comments at the moment.