3920. 数列(NOIP2021)
时间限制：1000 MS 内存限制：512 MB
题目描述
## 题目描述 给定整数 $ n,m,k $ ，和一个长度为 $ m+1 $ 的正整数数组 $ v_0,v_1,\cdot\cdot\cdot,v_m $。 对于一个长度为 $ n $，下标从 1 开始且每个元素均不超过 $ m $ 的非负整数序列 $ \{a_i\} $，我们定义它的权值为 $ v_{a_1}\timesv_{a_2}\times\cdot\cdot\cdot\timesv_{a_n} $。 当这样的序列 $ \{a_i\} $ 满足整数 $ S=2^{a_1}+2^{a_2}+···+2^{a_n} $ 的二进制表示中 $ 1 $ 的个数不超过 $ k $ 时，我们认为 $ \{a_i\} $ 是一个合法序列。 计算所有合法序列 $ \{a_i\} $ 的权值和对 $ 998244353 $ 取模的结果。 ## 输入格式 输入的一行是三个整数 $ n,m,k $。 第二行 $ m+1 $ 个整数，分别是 $ v_0,v_1,\cdot\cdot\cdot,v_m $。 ## 输出格式 仅一行一个整数，表示所有合法序列的权值和对 $ 998244353 $ 取模的结果。 ## 数据范围 对所有测试点保证 $ 1\lek\len\le30,0\lem\le100,1\lev_i<998244353 $。  ```in4 5 1 1 2 1 ``` ```out4 40 ``` ## 说明 由于 $ k=1 $ ，而且由 $ n\leS\len\times2^m $ 知道 $ 5\leS\le10 $，合法的 $ S $ 只有一种可能： $ S=8 $ ，这要求 $ a $ 中必须有 $ 2 $ 个 $ 0 $ 和 $ 3 $ 个 $ 1 $ ，于是有 $ {C}_{5}^{2}=10 $ 种可能的序列，每种序列的贡献都是 $ v^2_0 v^3_1=4 $，权值和为 $ 10\times4=40 $。