数列

题目描述:

给定整数 n,m,k，和一个长度为 m+1 的正整数数组 v0​,v1​,…,vm​。

对于一个长度为 n，下标从 1 开始且每个元素均不超过 m 的非负整数序列 {ai​}，我们定义它的权值为 va1​​×va2​​×⋯×van​​。

当这样的序列 {ai​} 满足整数 S=2^a1​+2^a2​+⋯+2^an​ 的二进制表示中 1 的个数不超过 k 时，我们认为{ai​} 是一个合法序列。

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

输入格式:

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

第二行 m+1 个整数，分别是 v0​,v1​,…,vm​。

输出格式:

样例输入:

5 1 1
2 1

样例输出:

40

提示:

【样例解释 #1】

由于 k=1，而且由 n≤S≤n×2^m 知道 5≤S≤10，合法的 S 只有一种可能：S=8，这要求 a 中必须有2 个 0 和 3 个 1，于是有 C(5,2)=10 种可能的序列，每种序列的贡献都是v0²​v1³​=4，权值和为 10×4=40。

【数据范围】

对所有测试点保证 1≤k≤n≤30，0≤m≤100，1≤vi​<998244353。

时间限制: 1000ms
空间限制: 512MB

---

来源: NOIP2021提高2