题目描述
给定整数 n,m,k,和一个长度为 m+1 的正整数数组 v0,v1,…,vm 。
对于一个长度为 n ,下标从 1 开始且每个元素均不超过 m 的非负整数序列 {ai} ,我们定义它的权值为 $v_{a_1} \times v_{a_2} \times \cdots \times v_{a_n}$ 。
当这样的序列 {ai} 满足整数 S=2a1+2a2+⋯+2an 的二进制表示中 1 的个数不超过 k 时,我们认为 {ai} 是一个合法序列。
计算所有合法序列 {ai} 的权值和对 998244353 取模的结果。
输入格式
从文件 sequence.in
中读入数据。
输入第一行是三个整数 n,m,k 。
第二行 m+1 个整数,分别是 v0,v1,…,vm 。
输出格式
输出到文件 sequence.out
中。
仅一行一个整数,表示所有合法序列的权值和对 998244353 取模的结果。
5 1 1
2 1
40
样例1解释:
由于 k=1 ,而且由 n≤S≤n×2m 知道 5≤S≤10 ,合法的 S 只有一种可能:S=8 ,这要求 a 中必须有 2 个 0 和 3 个 1 ,于是有 (25)=10 种可能的序列,每种序列的贡献都是 v02v13=4 ,权值和为 10×4=40 。
样例2:
见选手目录下的 sequence/sequence2.in
与 sequence/sequence2.ans
。
数据范围
测试点 |
n |
k |
m |
1−4 |
=8 |
≤n |
=9 |
5−7 |
=30 |
=7 |
8−10 |
=12 |
11−13 |
=1 |
=100 |
14−15 |
=5 |
≤n |
=50 |
16 |
=15 |
=100 |
17−18 |
=30 |
=30 |
19−20 |
=100 |