拉格朗日插值优化DP
第一类：减少范围
发现答案是个 \(k\) 次多项式，即使值域很大，也可以直接通过前 \(k+1\) 项的值得到答案
例题一：P5469 NOI2019] 机器人
设 \(f_{l,r,i}\) 表示考虑区间 \([l,r]\)，其最大值为 \(i\) 的方案数，\(g_{l,r,i}\) 是 \(f_{l,r,i}\) 关于 \(i\) 的前缀和。转移就考虑枚举最后一个最大值位置。
考试时没有发现 \(f_{l,r,i}\) 是关于 \(i\) 的 \(2(r-l+1)\) 个 \(r-l\) 次多项式。
这是因为我把dp转移式写得太复杂度，通过组合意义或简单代换推导可以使dp式子变得简单，易于发现性质。
更组合意义的说明
考虑一个简化的问题。
设 \(f_{x,v}\) 表示 \(x\) 的子树中的最大值是 \(v\) 的方案数，要求父亲的权值一定比儿子大，且权值两两不同，\(f_{x,v}\) 是关于 \(v\) 的 \(siz_x -1\)次多项式。
证明就是，假设 \(x\) 的权值为 \(v\)，那么需要将 \(\{1,\cdots,v-1\}\) 分给剩下 \(siz_x-1\) 个节点，并组成一个堆，而由于组成堆的数量仅与数的形态有关，树的形态是不变的，组成堆的数量就不变，可以看作常数 \(H_x\)。
所以 \(f_{x,v}={v-1\choose siz_x-1}H_x\)， 这很明显是一个 \(siz_x-1\) 次多形式。
回到本题，首先可以将每个点的点权看作二元组 \((v,id)\) ，其中 \(v\) 是真实点权，\(id\) 是下标，那么就保证元素两两不同，其次枚举的 \(O(1)\) 的分界点是相加，如果可以组成多项式，不会影响次数。所以原问题可以转化为上述问题，多项式的结论仍然成立。
于是在dp的时候用拉格朗日插值做就可以了。复杂度 \(O(n^3\log n)\)。
这类拉格朗日插值优化dp的最大特点在于：
- 转移只有乘法与加法
- 对应位置转移，即 \(f_v\times g_v\to h_v\)，这有点像线段树合并
- 初始状态简单，为简单低次多项式。
- 去除值域的区间限制后，形成一个多项式，加上值域的区间限制后，就是若干段多项时
- 大多为树形结构dp，次数为 \(siz_x\pm o(1)\)。
例题二：P8290 [省选联考 2022] 填树
我的题解
第二类：优化转移
对于一个卷积 \(F(x)=G(x)H(x)\)，暴力算是 \(\mathcal O(n^2)\)，可以直接带入 \(x\in [0,n]\) 可以做到 \(\mathcal O(n)\)，最后再一次拉插 \(\mathcal O(n^2)\)。由于拉插复杂度高，当仅当转移次数较大时，比如 \(\mathcal O(n)\) 次转移。