TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P8936
  • 题目
  • P8936[NOIP2021] 数列
    限制 : 时间限制 : - MS   空间限制 : 524288 KB
    评测说明 : 1s,512MB
    问题描述

    给定整数 \(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\) 取模的结果。

    样例输入

    5 1 1
    2 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\)

    大样例下载