Logo Infinity Online Judge

InfOJ

时间限制:1 s 空间限制:512 MB

#117. [NOIP2021] 数列

统计

数据组成

由官方数据 + infoj 民间数据组成(民间数据存在于 extra test 中)。

题目描述

给定整数 $n, m, k$,和一个长度为 $m + 1$ 的正整数数组 $v_0, v_1, \ldots, 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, \ldots, 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$,于是有 $\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$