搜索

P7961 数列 题解


发布时间: 2022-11-25 00:17:01    浏览次数:29 次
  • 对模拟的过程不敏感,对范围的数字不敏感

  • 手玩是发现规律的好方式

  • 计数 dp 以及一众计数题是明显短板,需要加紧突破。

样例解释已经较为明显地提示了这道题的大致做法。对于计数题,有动归与组合数学两种方法。但这道题并不是很能推式子,所以采用动态规划。

我们需要统计 \(0\)\(m\) 每个元素的个数,所以要有一维记录当前推到第几个元素。

答案与整数 \(S\) 有较大关联,我们需要一维记录当前递推到 \(S\) 第几位。

发现根据上面两维无法表示 \(1\) 的 数量不超过 \(k\) 个,于是要再开一维表示当前 \(S\) 有几个 \(1\)

但是由于每个点可以选多次,所以我们只凭这些,最终 \(1\) 的个数还是无法确定。

我们得到了一个半成品数组,\(dp_{i,j,k}\) 表示当前推到第 \(i\) 个元素,推到第 \(j\) 位,当前有 \(k\)\(1\) 的答案。

如果你推到这里卡住了,没有关系。你需要的是查看一众 NOI 拿金游记并睡一觉。

试着根据这个半成品数组设计转移方程,我们发现由于有 \(1\) 的个数存在,并不是很好推这个状态是由哪些状态转移而来得到,但我们只需枚举当前第 \(i\) 个元素选了几个,就可以推出这个状态对后面状态的贡献。通过枚举选了 \(t\) 个,我们可以得出当前的位是 \(0\) 还是 \(1\),但是尽管同样是 \(1\),选 \(1\) 个和选 \(3\) 个还是有很大的不同的。这会影响下一位的值,也许还会影响下下位的。

发现实际上,这个影响取决于进位的多少。所以我们还需要一维,表示当前一位要向后进多少的值。

成品数组产生了:\(dp_{i,j,k,w}\) 表示当前推到第 \(i\) 个元素,推到第 \(j\) 位,当前有 \(k\)\(1\) ,且要向下一位进 \(w\) 的值。显然, \(w\) 最大就是 \(n\),因为当前元素最多选 \(n\) 个。

贡献是多少?\(dp_{i,j,k,w}\) 实际上就是一种方案的权值乘上这种方案产生的序列个数。显然,现有的权值要乘上 \(p_i\)。产生的序列个数就是在选剩的格子里(共 \(n-j\) 个)选 \(t\) 个填上的方案乘上原来的方案。根据结合律可得:

f[i + 1][j + t][w + ((t + p) % 2)][(t + p) / 2] += ((((f[i][j][w][p] * qp[i][t]) % mod) * C[n - j][t]) % mod);

最后统计答案时要注意,第 \(n\) 位的进位也要加以判断。实际上就是求进位数的 popcount ,如果这个和原来的 \(k\) 加起来不大于题目要求才可被统计。

免责声明 P7961 数列 题解,资源类别:文本, 浏览次数:29 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-25 12:17:01。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/closureshop/p/16916635.html