一道有趣计数题的 O(n^2) 做法

tobie · 2024-12-04 22:27:25 · 算法·理论

从 CF1943D2 的 这篇题解 的同类题里找到的东西，还挺有意思的。

给定序列 w，定义一个长度为 n 的序列 a 的权值为 \prod_{i=1}^{n-2} w_{\max(a_i,a_{i+1},a_{i+2})}，求所有值域为 [0,n] 的非负整数序列的权值和。

首先有一个非常暴力的dp：f_{i,x,y} 表示当前考虑到 i，最后两个位置分别为 x 和 y 的权值和。转移可以用前缀和优化到 O(n^3)。

接下来我们发掘一下性质。注意到，如果 x>y，则 y 的取值和当前的 dp 值没有关系。所以考虑在这个情况下先不去钦定 y 具体是多少。

所以考虑优化状态设计：

转移考虑新的最大值是谁。

• [x\le y]f_{i,x}\times w_y\to f_{i+1,y}
• f_{i,x}\times w_x\to g_{i+1,x}
• [x\le y]g_{i,x}\times w_y\times x\to f_{i+1,y}
• [x>y] g_{i,x}\times w_x\times (y+1)\to f_{i+1,y}
• [x>y] g_{i,x}\times w_x\to g_{i+1,y}

转移可以使用前缀和优化做到 O(n^2)。

和 CF1943D2 一样，一个很重要的思想就是思考什么东西是“不重要”的，对于 CF1943D2 来说是当 i 不合法时 i-1 的合法性，对于本题来说是当 a_{i-1}>a_i 时 a_i 的具体取值。