当前位置:首页 > 搜索 > 记忆化搜索 > 正文
洛谷P7961数列(NOIP2021)
1539+

题目大意:一个n个数的序列a,每个数范围是0~m,要求$\sum{2^{a_i}}$的二进制中1的数个不超过w,有多少中方案?方案的权值之和($\sum{\prod{v_{a_i}}}$)是多少?

题目描述

给定整数 $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

输入样例 #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$ |

解题思路

数据范围比较小,爆搜可以骗分。

方案一:暴力枚举序列中的每个数字,时间复杂度$O(n^m)$,排列存在大量重复,也不太好优化。

方案二:暴力枚举每个二进制位有多少个,时间复杂度$O(m^n)$,重复可以用组合数学优化。

程序实现

方案一优化后时间复杂度:$O(n*n*2^m*m)$,50分。

爆搜后记忆化即可:填到序列第k个数,当前的和为x,后面剩下数字一样、需要凑的1也一样,算过可以直接返回答案。

方案二优化后时间复杂度:$O(m*n^4)$,满分。

首先,预处理组合数c[i][j]表示$C_i^j$,预处理权值次幂s[i][j]表示选j个i次幂的乘积,然后进行爆搜与记忆化。

逐个格子填入数量,并一边爆搜一般记录低位1的数量、高位1的数量。

技巧1:从低次幂开始爆搜,所以后面高次幂的1对前面低次幂没有影响。

技巧2:高次幂的1只需要记录最低位的即可,因为拆来拆去都是等价的。由于高次幂的1由低次幂凑成,所以数量不超过n。

记忆化:填到$2^k$的数量时,低位1确定,高位1也确定(相当于数字的值确定,因为后面只受高位1影响),剩下的幂的数量也确定,下次搜到同样状态时,可以时间返回之前计算的答案,避免重复搜索。

加乘原理:后面有很多中方案,增加一个数后,这个数需要乘以后面每一种方案的权值;我们可以先将后面的方案权值之和求出来,后面直接乘即可。

组合数学:剩下的幂有n-u个,当前的幂选择i个,存放的位置有c[n-u][i]个,每一种权值之和都有那么多中方案。

递归结束条件:填完了但数量不对返回零;序列a足够n个了,只要满足条件就是一种合法方案。

(感谢mekoszc提供考场代码)

洛谷P7961数列(NOIP2021):等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!