3914 - 数列

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 1 秒

内存限制 : 128 MB

输入

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

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

输出

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

样例

输入

5 1 1
2 1

输出

提示

【样例解释 #1】

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

【数据范围】

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

测试点	$n$	$k$	$m$
$1 \sim 4$	$=8$	$\leq n$	$=9$
$5 \sim 7$	$=30$	$\leq n$	$=7$
$8 \sim 10$	$=30$	$\leq n$	$=12$
$11 \sim 13$	$=30$	$=1$	$=100$
$14 \sim 15$	$=5$	$\leq n$	$=50$
$16$	$=15$	$\leq n$	$=100$
$17 \sim 18$	$=30$	$\leq n$	$=30$
$19 \sim 20$	$=30$	$\leq n$	$=100$

来源

NOIP