A4615 | [NOIP2021] 数列
来源NOIP提高组 / 2021
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
NOIP2021 T2
给定整数 $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$。
对于一个长度为 $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$。
第二行 $m + 1$ 个整数，分别是 $v_0, v_1, \ldots, v_m$。
输出格式
仅一行一个整数，表示所有合法序列的权值和对 $998244353$ 取模的结果。
输入输出样例
输入 #1
5 1 1 2 1
输出 #1
40
输入 #2
见附件中的 sequence/sequence2.in
输出 #2
见附件中的 sequence/sequence2.ans
**【样例解释 #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$ |
**【附件下载】**
[sequence.zip](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/gav0uclm)
由于 $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$ |
**【附件下载】**
[sequence.zip](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/gav0uclm)
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？