菜王的 blog

好题。碍于场上策略原因没有场切这个题，但也算是单杀了，来写篇题解。

首先这个平方和就很可以拆，直接变成选两条长度为 $l$ 的链，在任意一条链上的点颜色均相同，其它点颜色任意的方案数。

这个东西就可以直接 DP 了，可以直接导出一个 $O(n^3l^2)$ 的做法，具体地，设 $f_{u, v, x, y}$ 表示两条链走到 $u, v$，长度分别为 $x, y$ 的方案数，每次转移拓扑序更小的点并处理 $u = v$ 的情况即可。

但是这个做法并没有什么优化空间，又因为题目中 $n$ 比 $l$ 更大，所以我们更倾向于一个 $O(n^2poly(l))$ 的做法。发现记录两个点是没有必要的，只需要记录它们重合的位置。即，设 $f_{u, x, y}$ 表示两条链最后一次重合在 $u$，长度分别为 $x, y$ 的方案数，每次转移时枚举下一个重合的位置。但是这样转移的系数是不好算的。

那么我们放弃钦定它们在途中不重合，改为钦定它们重合的次数，最后用二项式反演得出恰好重合这么多次的答案。具体来说，设 $f_{u, x, y, i}$ 表示两条链最后一次重合在 $u$，长度分别为 $x, y$，钦定重合了 $i$ 次的方案数，$g_{u, v, i}$ 表示 $u$ 走到 $v$ 恰好走 $i$ 条边的方案数，那么有转移方程：

$f_{u, x, y, i} \times g_{u, v, p} \times g_{u, v, q} \to f_{v, x + p, y + q, i + 1}$

然后设 $h1_i$ 为钦定重合了 $i$ 次的总方案数，$h2_i$ 为恰好重合了 $i$ 次的总方案数，有：

$h2_i = h1_i - \sum_{j = i + 1}^l \binom ji h2_j\\ ans = \sum_{i = 0}^l k^{n - 2l + i + 1} h2_i$

直接转移即可做到 $O(n^2l^5)$。发现转移是一个二维卷积，但可以变成两次一维卷积，可以优化到 $O(n^2l^4)$，然后就可以获得 $84$ 了。考虑那个 $i$ 维与转移无关，尝试优化。

我们考虑另一种二项式反演：

$h2_i = \sum_{j = i}^l \binom ji (-1)^{j - i} h1_j\\ \begin{aligned} ans &= \sum_{i = 0}^l k^{n - 2l + i + 1} h2_i\\ ans &= \sum_{i = 0}^l k^{n - 2l + i + 1} \sum_{j = i}^l \binom ji (-1)^{j - i} h1_j\\ &= k^{n - 2l + 1} \sum_{j = 0}^l h1_j \sum_{i = 0}^j k^i (-1)^{j - i}\binom ji\\ &= k^{n - 2l + 1} \sum_{j = 0}^l h1_j (k - 1)^j\\ \end{aligned}$

那么我们在转移过程中将系数乘上去即可，这样就省掉了 $i$ 维。时间复杂度为 $O(n^3l + n^2l^3)$。