DP特训总结（欲望加速）

像题解/游记一样的东西挂在这里了。
技巧之类的东西挂在这里了。

E - 「KDOI-11」彩灯晚会

不妨猜测，这里的平方只需要维护 \(0/1/2\) 次项就能过，即它带来的复杂度是 \(O(1)\) 的。发现不行。

不妨拆贡献，发现不行。

不妨考虑平方的组合意义。可以在原图中选任意两条点数为 \(l\) 的链，定义一条链的权值为其边权的乘积，一个选择方案的权值为其两条链权值的乘积，那么答案即为所有选择方案的权值和。

看起来非常酷炫！不过这里相当于是在对只有一种颜色的图计数。考虑上颜色其实也比较简单，我们只需要这两条链的点集的并同色就行了。

到这里就有一个酷炫的 DP 做法。设 \(dp_{u1,u2,l1,l2}\) 表示两条链开头分别是 \(u1\) 和 \(u2\)，长度分别是 \(l1\) 和 \(l2\) 时的答案。每次转移选 \(u1,u2\) 中拓扑序较小的点走一步，如果 \(u1=u2\) 就优先走 \(u1\)。设 \(c\) 为两条链的交集大小，那么一种选择方案对应的染色数就应该是 \(k^{n-2l+c+1}\)。于是每次发现 \(u1=u2\) 时再额外乘一点东西就行了。这个显然是对的。时间复杂度 \(O(n^3l^2)\)。

优化不了。很烦。注意到我们只关心交集的大小，所以也许状态里只需要记交集中的点。

设 \(dp_{u,l1,l2,c}\) 表示两条链最后一次相交在点 \(u\)，长度分别是 \(l1\) 和 \(l2\)，且交点共有 \(c\) 个时的方案数。这样做直接做就是 \(O(n^2l^5)\) 的。可以预处理 \(g_{u,v,l}\) 表示 \(u\) 到 \(v\) 长度为 \(l\) 的路径数量，发现要套一层二项式反演。

两维卷积可以分部算，复杂度 \(O(n^2l^4)\)。

怎么优化呢？推一推式子，发现外层的二项式反演可以拆开，只需要在转移时搞一点系数就行了。于是 \(c\) 那一维不用记录了。时间复杂度 \(O(n^2l^3)\)，可过。

F - 构造数组

好题啊。

D - Subtree Value

考虑我们能做什么。设 \(g(x,k)\) 表示，附加权值为 \(k\) 时所有大小为 \(x\) 的连通块的权值之和。我们可以在固定 \(k\) 的情况下求出所有 \(g(x,k)\)，其中 \(x\in[1,n]\)。

容易发现，\(g(x,kU+r)\) 在 \(x,U,r\) 均为定值的情况下是一个关于 \(k\) 的 \(V-1\) 次多项式（在模 \(U^V\) 意义下）。而我们要求的是所有 \(g(x,x)\)，因为只有当附加权值等于连通块大小时，我们算的才是对的。因此，可以先枚举 \(r\)，再对 \(k\in[0,V-1]\) 求出所有的 \(g\)，然后插值得到 \(n\) 个多项式。这下，对于每个满足 \(x=kU+r\) 的 \(x\)，我们就都能求出答案了。要求的 \(g(x,i)\) 的 \(i\) 共有 \(O(UV)\) 个，要插值的多项式共有 \(O(n)\) 个（我们只需要有需要的多项式，如果 \(g(x,i)\) 的 \(x\) 不等于 \(kU+r\)，我们可以不插值。）

由于不一定有逆元，可以使用如下插值：

\[f(k)=\sum\limits_{i=1}^n C_{k-1}^{i-1} \sum\limits_{j=1}^i (-1)^{i+j} C_{i-1}^{j-1}f(j) \]

我不会证明，geven 说当结论记。

求 \(g\) 的总复杂度是 \(O(n^2UV)\) 的，插值的复杂度是 \(O(nV^2)\) 的，然后就能过了。

H - 「KDOI-12」能做到的也只不过是静等缘分耗尽的那一天。

怎么做，\(\sum\limits_{i=1}^n i C_{i}^x\)？？？（我们假设 \(1\leq x \leq n\)。）

发现，\(\sum\limits_{i=1}^n C_i^x = C_{n+1}^{x+1} = \frac{(n+1)!}{(x+1)!(n-x)!}\)。

又发现，\(\sum\limits_{i=1}^n C_i^x = \sum\limits_{i=1}^n \frac{i!}{x!(i-x)!}\)，而我们要求的是 \(\sum\limits_{i=1}^n \frac{i!\times i}{x!(i-x)!}\)。尝试凑一凑系数，先搞一个 \(\sum\limits_{i=1}^n \frac{(i+1)!}{x!(i-x)!}\)，再用它减去 \(\sum\limits_{i=1}^n\frac{i!}{x!(i-x)!}\) 就行了。容易发现 \(\sum\limits_{i=1}^n \frac{(i+1)!}{x!(i-x)!} = (x+1)\sum\limits_{i=1}^n \frac{(i+1)!}{(x+1)!(i-x)!}=(x+1)\sum\limits_{i=1}^n C_{i+1}^{x+1}=(x+1)C_{n+2}^{x+2}\)。

所以 \(\sum\limits_{i=1}^n iC_{i}^x=(x+1)C_{n+2}^{x+2}-C_{n+1}^{x+1}\)。（咨询了 Deepseek。）

然而，这个东西和正解没什么关系。但是和 wxir 的正解有点关系。不过 wxir 和正解没有什么关系。所以这个东西和正解没有什么关系。下面说的东西才是正解，它和 wxir 没有什么关系。

技巧：现在若要计数排列 \(p\)，还需要满足 \(p_x\) 是 \([l,r]\) 里的最大值，可以考虑转化成树上拓扑序。