Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5637 --数列
5637: 数列
警告!
题目
状态
题解
题目描述
给定整数 $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$ |
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
提高+/省选-
标签
点击显示
if ($pr_flag) { ?>
递交数
7
已通过
4
} ;?>
通过率
58%
时间限制
1 秒
内存限制
512 MB
来源
NOIP2021
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和