NOIP '21 P2 - Sequence

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

You are given integers n, m, k and m+1 positive integers v_0, v_1, \dots, v_m.

For a one-based array \{a_i\} containing n integers between 0 and m, its weight is defined as v_{a_1} \times v_{a_2} \times \dots \times v_{a_n}.

Such an array \{a_i\} is valid if S = 2^{a_1} + 2^{a_2} + \dots + 2^{a_n} contains no more than k ones in its binary representation.

Calculate the sum of weights of all valid arrays \{a_i\}. Output the sum modulo 998\,244\,353.

Input Specification

The first line contains 3 integers n, m, k.

The second line contains m+1 integers v_0, v_1, \dots, v_m.

Output Specification

Output a single integer, the sum of weights of all valid arrays modulo 998\,244\,353.

Sample Input

5 1 1
2 1

Sample Output


Sample 1 Explanation

Because k is 1 and n \le S \le n \times 2m implies 5 \le S \le 10, there is only one possible S: S = 8. This requires that a contains two 0s and three 1s. Thus, we have \left(\begin{array}{c}5\\2\end{array}\right)=10 valid arrays. Each array has weight v_0^2 v_1^3 = 4. The sum is 40.

Additional Samples

Additional samples can be found here.


For all test cases, 1 \le k \le n \le 30, 0 \le m \le 100, 1 \le v_i < 998\,244\,353.

Test cases n k m
1\sim 4 =8 \le n =9
5\sim 7 =30 =7
8\sim 10 =12
11\sim 13 =1 =100
14\sim 15 =5 \le n =50
16 =15 =100
17\sim 18 =30 =30
19\sim 20 =100


There are no comments at the moment.