3625. [NOIP 2021]数列

【题目描述】

给定整数 $n,m,k$，和一个长度为 $m + 1$ 的正整数数组 $v_0,v_1,\cdots, v_m$。

对于一个长度为 $n$，下标从 1 开始且每个元素均不超过 $m$ 的非负整数序列 $\{a_i\}$，我们定义它的权值为 $v_{a_1}\times {v_{a_2}}\times \cdots\times v_{a_n}$。

当这样的序列 $\{a_i\}$ 满足整数 $S=2^{a_1}+2^{a_2}+\cdots+2^{a_n}$的二进制表示中 1 的个数不超过 $k$ 时，我们认为 $\{a_i\}$ 是一个合法序列。

计算所有合法序列 $\{a_i\}$ 的权值和对 998244353 取模的结果。

【输入格式】

输入的第一行是三个整数 $n,m,k$。

第二行 $m + 1$ 个整数，分别是 $v_0,v_1,\cdots, v_m$。

【输出格式】

仅一行一个整数，表示所有合法序列的权值和对 998244353 取模的结果。

【样例1输入】

5 1 1
2 1

【样例1输出】

40

【样例1说明】

由于$k=1$，而且由$n\leq S\leq n\times 2^m$知道$5\leq S\leq 10$，合法的$S$只有一种可能：$S=8$，这要求$a$种必须有2个0和3个1，于是有$({}^{5}_{2})=10$种可能的序列，每种序列的贡献都是$v_0^2v_1^3=4$，权值和为$10\times 4=40$。

【样例2】

下载

【数据规模与约定】

对所有测试点保证$1\leq k\leq n\leq 30, 0\leq m\leq 100,1\leq v_i<998244353$。

【来源】

NOIP 2021 Task2