剩下的题有些不可做,可做的也懒得去写了。(咕咕咕
DifferenceSequence
定义对一个序列进行一次操作为
A1,A2,…,An→∣A1−A2∣,∣A2−A1∣,…,∣An−A1∣
对于任意一个序列,进行操作后必然会进入一个循环。我们定义循环内的最大字典序串为此串的代表串,求所有长度为 n 的串的代表串去重后字典序第 k 小的串。
我们先打个表观察一下会发现,任意一个序列在进行很多次操作后都会变成一些相同大小的数字与 0 组成的串一直循环。再发现 n≤26 于是可以枚举所有的二进制串,看看它在进入循环后是否已经有被其他二进制串统计过了,如果没有就把最大的串放入答案。
由于一个串进行操作后得到的串只会被便历一遍,使用位运算来操作,这样做的复杂度是 O(226) 。
UniqueMST
看了题解才懂。
我们设 F(n,k) 表示 n 个点的完全图,每个边边权在 [1,K] 内,最终最小生成树唯一且生成树上的边权 ≤k 的方案数。
我们考虑枚举一下除开权值是 k 的边时每个最小生成树部分的大小,假设在不加入权值 =k 的边的时候最小生成树的连通块是 x1,x2,…,xr ,且 x1 是 1 所在的连通块大小,x2 是除开第一个连通块后最小的点所在的连通块大小 … ,同时我们假设这些连通块本身的导出子图已经被确定好了边权,于是它们的贡献就是
(x1−1n−1)(x2−1n−x1−1)⋯∏F(xi,k−1)
然后考虑如何给树之间连边。考虑 prufer
序。根据口罩那题的经典结论,在加入权值等于 k 的边后的树的形态种数是
nr−2∏xi
然后还需要考虑对不在树上剩下的边定权值,这些边权值必须是 (k,K] ,其中 K 是最大的可以用的边权。这部分的贡献是
(K−k)(2n)+1−∑((2xi)+1)
所以总的式子就是
F(n,k)=n21∑xi=n∑((x1−1n−1)(x2−1n−x1−1)⋯)(K−k)(2n)+1−∑((2xi)+1)i≤r∏nxiF(xi,k−1)
可以发现 F(n,k) 可以 dp 求得。具体来说,考虑如何计算 F(n,k) ,由于最后那个 ∏ 里面有一个 n ,必须再做一次 pd[x] 表示一共是 n 个点,当前有了 x 个点,转移就是加入一个连通块,贡献是显然的。最后再用 pd[n] 推到 F(n,k) 。这样做复杂度是 O(n3k) 。
这题 k 竟然是 109 ,可以想到会不会是插值。考虑把 F(n,k) 看成一个关于 k 的多项式。其实直接求 n2 个点值做插值就能过了。实际分析出来多项式的次数是 (2n) 的。考虑归纳证明。考虑 r≥2 的情况,假设 F(xi,k−1) 次数是 (2xi) ,那么实际上次数是
(2n)+1−∑((2xi)+1)+∑(2xi)≤(2n)−1
而如果 r=1 ,即贡献是 F(n,k−1) 的次数。也就是说 F(n,k)−F(n,k−1) 次数是 (2n)−1 ,做前缀和后次数显然就是 (2n) 。
这玩意显然可以 O(n4) 插值。具体实现可以直接把 k 代进拉格朗日插值式子里面。
CannonballPyramids
还是先打表,会发现前 3×106 的数只有不到 1000 的时候才可能需要六个数,大于 1000 的时候一定只需要少于 6 个数。于是我们考虑对于 x 我们找出小于它最大的 6n(n+1)(2n+1) 然后减掉它,不难发现得到的数一定少于 2.25×106 左右。于是如果差值不到 1000 则找次大的来做,否则直接输出方案即可。
复杂度看起来很大,本机也很慢,但是交上去跑过去了。。
CardConcat
直接做 dp 可能会有一些复杂度比较高且不太好写的做法。于是可以考虑每个数的贡献。具体来说,我们考虑对于一个数,我们从它前面选择 j 个数,从它后面选择 k 个数,把这些数放到它的后面,于是就会导致它有 10 的这些数字的数位和次方的贡献,这歌贡献是可以通过对前后缀做一个背包处理的。然后还需要算出在剩下的 n−1−j−k 个数随便选择并排列好的方案数。这个也是非常好求的。
于是总复杂度 O(n3) 可以通过。
TwoPerLine
按照套路,我们可以把 (x,y) 的棋子看成是二分图左侧的 x 和右侧的 y 之间的一条连边。于是现在问题就变成了给定 n,m 求有多少种二分图满足有 m 条边,且每个点度数不超过 2 。一种非常显然的想法是设 dp[l][r][a] 表示左边有 l 个点度数是 1 ,右边有 r 个,且一共已经连了 a 条边。我们考虑左边的情况,假设有 x 个点度数是 0 ,y 个是 2 于是有
2y+l=ax+y+l=n
发现可以解出 x,y 。
但是还是存在一个问题。在连边的时候,如果我们想要给两个度数为 1 的点连边,会发现我们并不知道这两个点之间是否已经存在边了。这个问题看起来很不可处理,可能需要多开好几维来解决。这个时候可以想到容斥掉这种情况,也就是说我们钦定最后图种会有 k 条长成这样的重边存在,系数就是 (−1)k 。那么我们可以在转移中增加一种,在两个度数为 0 的点间一次性连两条边。注意连第二条边的时候我们需要乘上一个 m−a−1 ,因为需要给他钦定一个连入的时间,这样才可以方便去重。
复杂度 O(n4) 。
\