一些 Topcoder DP题 题解

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

DifferenceSequence

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

A1,A2,,AnA1A2,A2A1,,AnA1A_1,A_2,\dots ,A_n\\ \to |A_1-A_2|,|A_2-A_1|,\dots ,|A_n-A_1|

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

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

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

UniqueMST

看了题解才懂。

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

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

(n1x11)(nx11x21)F(xi,k1)\binom{n-1}{x_1-1} \binom{n-x_1-1}{x_2-1} \cdots\prod F(x_i,k-1)

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

nr2xin^{r-2}\prod x_i

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

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

所以总的式子就是

F(n,k)=1n2xi=n((n1x11)(nx11x21))(Kk)(n2)+1((xi2)+1)irnxiF(xi,k1)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)F(n,k) 可以 dpdp 求得。具体来说,考虑如何计算 F(n,k)F(n,k) ,由于最后那个 \prod 里面有一个 nn ,必须再做一次 pd[x]pd[x] 表示一共是 nn 个点,当前有了 xx 个点,转移就是加入一个连通块,贡献是显然的。最后再用 pd[n]pd[n] 推到 F(n,k)F(n,k) 。这样做复杂度是 O(n3k)O(n^3 k)

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

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

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

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

CannonballPyramids

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

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

CardConcat

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

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

TwoPerLine

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

2y+l=ax+y+l=n2y + l = a\\ x + y + l = n

发现可以解出 x,yx,y

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

复杂度 O(n4)O(n^4)

\