2024.5

1. pkuwc2024 d2t2 排序

暴力就是按值从大到小填，记录初始序列有哪些位置被填了，每次填上一个数计算它与比它大的数之间的交换次数，模拟一下希尔排序，这个做法是 \(\mathcal{O}(2^nnm)\)。

先优化掉状态数，需要 swap 次数最多，那么按 \(d_1\) 分组后每组内部一定是递减的，将已经填入的看成 1，还未填入的看成 -1，当前填进去的数看成 0。首先状态只需要记每一组 -1 的个数，那么状态数到达了 \(\mathcal{O}\left(\left(\frac{n}{d_1}+1\right)^{d_1}\right)\) 级别，可以接受。转移相当于将某个 -1 填成 0，再计算 0 和 1 之间会产生多少次交换，然后再将 0 变成 1 。枚举在哪个位置填并转移是 \(\mathcal{O}(d_1)\)（或者 \(\mathcal{O}(n)\)） 的，问题在于怎样快速计算贡献。

这个时候发现可以记忆化搜索，或者说从 \(d_m\) 往前 dp 到 \(d_1\)。对于每个 \(d_i\) 记录每一组有多少个 -1 以及 0 在哪个位置，分组计算一下逆序对并且组内排序，进行 dp 的转移。这里状态数是 \(\mathcal{O}\left(\sum\limits_{i=1}^m\left(\frac{n}{d_i}+1\right)^{d_i}d_i\right)\) 的（要记 0 在哪一组），单次转移是 \(\mathcal{O}(n)\)。可以通过。

2. pkuwc2024 d1t2 最小值之和

抄写 skc 的题解，这里 \(a,a'\) 是原题面的 \(f,f'\)。

令 \(dp(l,r,k)\) 表示 \([l,r]\) 中的 \(a'\) 全部减去 \(k\) 是否存在构造，那么 \(dp(l,r,k)\gets dp(l,i,k+j(r-l))\And dp(i+1,r,k+j(r-l))\)，也就是在 \(a_i\) 处填 \(j\) 作为最小值，并且让 \([l,r)\) 中的所有 \(a\) 都减去 \(j\) 得以递归处理。

可以将 \([l,r)\) 中的 \(a\) 整体 +1，那么 \(dp(l,r,k)=1\) 则 \(dp(l,r,k-(r-l))=1\)，所以另设 \(f(l,r,k)=p\) 为最大的 \(p\equiv k\pmod{(r-l)}\) 且 \(dp(l,r,p)=1\)，考虑枚举 \(i\) 之后从 \(f(l,i,w_1)=p_1\) 和 \(f(i+1,r,w_2)=p_2\) 尝试给 \(f(l,r,*)\) 转移。

此时看 \(k+j(r-l)\) 可以为多少，解出 \(\left\{\begin{matrix}x\equiv w_1 \pmod {(i-l)}\\x\equiv w_2 \pmod {(r-i-1)}\end{matrix}\right.\) 并且满足 \(x\leq \min(p_1,p_2)\) 的最大非负整数解 \(x_0\)（这里不用写 exgcd 可以直接暴力），那么它就是能满足 \(x=k+j(r-l)\) 最大的 \(x\)，那么所有合法的 \(x=k+j(r-l)\) 通解形式为 \(x=x_0-t\operatorname{lcm}(i-l,r-i-1)\)，由于可以令 \(j=0\) 那么最大的 \(k\) 就是 \(x\)，所以对每个 \(t\) 将 \(f(l,r,x\bmod (r-l))\gets x\) 更新即可。

注意到只有 \(0\leq t<\frac{r-l}{\gcd(r-l,lcm)}\) 的 \(t\) 是有用的，暴力更新即可。区间 dp 是 \(\mathcal{O}(n^3)\) 的，枚举 \(w_1,w_2\) 是 \(\mathcal{O}(n^2)\) 的，枚举 \(t\) 是 \(\mathcal{O}(n)\) 的，常数极小已经可以通过。

优化就是考虑 dp 的更新形式就是同余最短路，那么将所有 \(f(l,r,x_0\bmod (r-l))\gets x\) 更新好，再将所有 \(lcm\) 拉下来跑同余最短路转两圈。外层枚举区间 \(\mathcal{O}(n^2)\)，枚举 lcm 是 \(\mathcal{O}(n^2)\)，转两圈更新 dp 是 \(\mathcal{O}(n)\)，这样复杂度是 \(\mathcal{O}(n^5)\) 的了。

3. pkusc2024 d1t3 独立

首先先小 N 的独立集那么做，那么现在问题就是初始 \(f_{x,1\cdots m}=1\)，然后树形 dp 合并子树的时候 \(f_{x,i}f_{v,j}\to f'_{x,\max(0,i-j)}\)，是个差卷积，能看出来 \(f_{x,i}\) 除了 \(i=0\) 以外的地方是关于 \(i\) 的 \(siz_x-1\) 次多项式，每个 \(x\) 对答案的贡献就是 \(\sum_i f_{x,i}\cdot i\cdot m^{n-siz_x}\)

欲求的 \(f_{x,i}\cdot i\) 前缀和是 \(siz_x+1\) 次多项式，所以尝试直接维护 \(n+2\) 个点值，想插值但是 \(1\sim n+2\) 项会和很多项有关，那么考虑求出倒数 \(n+2\) 项，也就是 \(m-n-1\sim m\) 项的系数，这里可以直接 \(\mathcal{O}(n\log n)\) 算一下差卷积，然后要将这些系数位移到 \(1\sim n+2\)，就是 P5667 拉格朗日插值2 这个题。

这里的技巧是尝试写卷积式子之后，想求第 \(x\) 项，但是其中一边的上界是 \(n\) 而不是 \(x\)，那么可以将另一边系数整体向右位移 \(n\) 项，这样卷出来的 \(n+x\) 项系数就是我们想要的。

\(m\leq n+2\) 的时候不用平移啥的之类的操作需要特判，直接差卷积合并 dp 就行。那么总的时间复杂度就是 \(\mathcal{O}(n^2\log n)\)。