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

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

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

• $f_{i,x}$ 表示当前最大值为 $a_i=x$ 的权值和。
• $g_{i,x}$ 表示当前最大值为 $a_{i-1}=x$ 的权值和，特别地，我们暂时认为 $a_{i}=0$，这个数具体是多少之后再钦定。

• $[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}$