一些 Topcoder DP题 题解

剩下的题有些不可做，可做的也懒得去写了。（咕咕咕

DifferenceSequence

定义对一个序列进行一次操作为

$A_1,A_2,\dots ,A_n\\ \to |A_1-A_2|,|A_2-A_1|,\dots ,|A_n-A_1|$

对于任意一个序列，进行操作后必然会进入一个循环。我们定义循环内的最大字典序串为此串的代表串，求所有长度为 $n$ 的串的代表串去重后字典序第 $k$ 小的串。

我们先打个表观察一下会发现，任意一个序列在进行很多次操作后都会变成一些相同大小的数字与 $0$ 组成的串一直循环。再发现 $n \le 26$ 于是可以枚举所有的二进制串，看看它在进入循环后是否已经有被其他二进制串统计过了，如果没有就把最大的串放入答案。

由于一个串进行操作后得到的串只会被便历一遍，使用位运算来操作，这样做的复杂度是 $O(2^{26})$ 。

UniqueMST

看了题解才懂。

我们设 $F(n,k)$ 表示 $n$ 个点的完全图，每个边边权在 $[1,K]$ 内，最终最小生成树唯一且生成树上的边权 $\le k$ 的方案数。

我们考虑枚举一下除开权值是 $k$ 的边时每个最小生成树部分的大小，假设在不加入权值 $=k$ 的边的时候最小生成树的连通块是 $x_1,x_2,\dots ,x_r$ ，且 $x_1$ 是 $1$ 所在的连通块大小，$x_2$ 是除开第一个连通块后最小的点所在的连通块大小 $\dots$ ，同时我们假设这些连通块本身的导出子图已经被确定好了边权，于是它们的贡献就是

$\binom{n-1}{x_1-1} \binom{n-x_1-1}{x_2-1} \cdots\prod F(x_i,k-1)$

然后考虑如何给树之间连边。考虑 prufer 序。根据口罩那题的经典结论，在加入权值等于 $k$ 的边后的树的形态种数是

$n^{r-2}\prod x_i$

然后还需要考虑对不在树上剩下的边定权值，这些边权值必须是 $(k,K]$ ，其中 $K$ 是最大的可以用的边权。这部分的贡献是

$(K-k)^{\binom n 2 + 1 - \sum (\binom {x_i} 2 + 1 )}$

所以总的式子就是

$F(n,k) = \frac 1 {n^2} \sum_{\sum x_i = n} \left( \binom{n-1}{x_1-1} \binom{n-x_1-1}{x_2-1} \cdots \right) (K-k)^{\binom n 2 + 1 - \sum( \binom{x_i}{2} + 1 )} \prod_{i \le r} nx_iF(x_i,k-1)$

可以发现 $F(n,k)$ 可以 $dp$ 求得。具体来说，考虑如何计算 $F(n,k)$ ，由于最后那个 $\prod$ 里面有一个 $n$ ，必须再做一次 $pd[x]$ 表示一共是 $n$ 个点，当前有了 $x$ 个点，转移就是加入一个连通块，贡献是显然的。最后再用 $pd[n]$ 推到 $F(n,k)$ 。这样做复杂度是 $O(n^3 k)$ 。

这题 $k$ 竟然是 $10^9$ ，可以想到会不会是插值。考虑把 $F(n,k)$ 看成一个关于 $k$ 的多项式。其实直接求 $n^2$ 个点值做插值就能过了。实际分析出来多项式的次数是 $\binom n 2$ 的。考虑归纳证明。考虑 $r \ge 2$ 的情况，假设 $F(x_i,k-1)$ 次数是 $\binom {x_i} 2$ ，那么实际上次数是

$\binom n 2 + 1 - \sum(\binom {x_i} 2 + 1) + \sum \binom {x_i} 2 \le \binom n 2 - 1$

而如果 $r = 1$ ，即贡献是 $F(n,k - 1)$ 的次数。也就是说 $F(n,k) - F(n,k-1)$ 次数是 $\binom{n}2 - 1$ ，做前缀和后次数显然就是 $\binom n 2$ 。

这玩意显然可以 $O(n^4)$ 插值。具体实现可以直接把 $k$ 代进拉格朗日插值式子里面。

CannonballPyramids

还是先打表，会发现前 $3 \times 10^6$ 的数只有不到 $1000$ 的时候才可能需要六个数，大于 $1000$ 的时候一定只需要少于 $6$ 个数。于是我们考虑对于 $x$ 我们找出小于它最大的 $\frac{n(n+1)(2n+1)}{6}$ 然后减掉它，不难发现得到的数一定少于 $2.25\times 10^6$ 左右。于是如果差值不到 $1000$ 则找次大的来做，否则直接输出方案即可。

复杂度看起来很大，本机也很慢，但是交上去跑过去了。。

CardConcat

直接做 $dp$ 可能会有一些复杂度比较高且不太好写的做法。于是可以考虑每个数的贡献。具体来说，我们考虑对于一个数，我们从它前面选择 $j$ 个数，从它后面选择 $k$ 个数，把这些数放到它的后面，于是就会导致它有 $10$ 的这些数字的数位和次方的贡献，这歌贡献是可以通过对前后缀做一个背包处理的。然后还需要算出在剩下的 $n-1-j-k$ 个数随便选择并排列好的方案数。这个也是非常好求的。

于是总复杂度 $O(n^3)$ 可以通过。

TwoPerLine

按照套路，我们可以把 $(x,y)$ 的棋子看成是二分图左侧的 $x$ 和右侧的 $y$ 之间的一条连边。于是现在问题就变成了给定 $n,m$ 求有多少种二分图满足有 $m$ 条边，且每个点度数不超过 $2$ 。一种非常显然的想法是设 $dp[l][r][a]$ 表示左边有 $l$ 个点度数是 $1$ ，右边有 $r$ 个，且一共已经连了 $a$ 条边。我们考虑左边的情况，假设有 $x$ 个点度数是 $0$ ，$y$ 个是 $2$ 于是有

$2y + l = a\\ x + y + l = n$

发现可以解出 $x,y$ 。

但是还是存在一个问题。在连边的时候，如果我们想要给两个度数为 $1$ 的点连边，会发现我们并不知道这两个点之间是否已经存在边了。这个问题看起来很不可处理，可能需要多开好几维来解决。这个时候可以想到容斥掉这种情况，也就是说我们钦定最后图种会有 $k$ 条长成这样的重边存在，系数就是 $(-1)^k$ 。那么我们可以在转移中增加一种，在两个度数为 $0$ 的点间一次性连两条边。注意连第二条边的时候我们需要乘上一个 $m-a-1$ ，因为需要给他钦定一个连入的时间，这样才可以方便去重。

复杂度 $O(n^4)$ 。