题解：P15038 「chaynOI R2 T3」合并同类项
xhabc66
·
·
题解
现令 y\leftarrow \min(x,y)，不劣。
发现在任意时刻，一个位置的数可以用原序列的一个连续段之和表示。
转换题意：两种操作都是合并连续段，只不过若有一连续段的和 \bmod k=0，则代价为 y，否则为 x。
不难发现情况 2 越多越好。那么我们就要使连续段之和为 0 的连续段出现的尽可能之多。
那么什么样的两个 0 连续段可以同时出现？考虑以下 3 种情况：
- 它们不交，这种情况下显然可以。
- 它们交但没有包含关系，显然不行。
- 它们存在包含关系，这种情况下可以现合并小段，再合并大段，所以也可以。
这种结构启示我们最终的 0 连续段可以通过将包含段与被包含段连边的方法建图，则最终图是森林。
不妨设被包含段是包含段的父亲，森林中所有根的父亲是连续段 [1,n]，考虑树形 dp。
考虑对于一个节点，考虑设它的状态为合并它的权值。如何转移？
最终的合并方案是一堆 0 区间拼起来，0 区间里的缝隙如何操作都是一样的。考虑对着这个东西 dp。设 dp_i 为此节点左端到 i 的子区间合并的最小权值，考虑转移。
显然的，转移就是选出一段以 i 结尾的区间，设其开头为 k，则 dp_i=\min(dp_k+1)。对于单个节点，这是 O(len^2) 的。能不能优化？分两类情况考虑：
- 若存在以 i 结尾的开头右于节点区间开头的和为 0 的连续段，则选左端点最左的一定不劣；
- 若不存在，则从 i-1 转移一定不劣。
那么现在转移就是 O(len) 的。极限情况下是 O(n^3) 的，过不了。
等等，注意到当 n>500 时有 k \ge 400，并且 \{a\} 是随机生成的，这有什么性质？
考虑对 \{a\} 的 \bmod\ k 意义下的前缀和数组 \{sum\}，那么 \{sum\} 显然也是随机生成的。同时，和为 0 的连续段个数等价于满足 0\le i<j \le n,sum_i=sum_j 的 (i,j) 的个数。考虑对于其中一个值 x，sum_i=x 的 i 的个数是 O(\dfrac{n}{k})，那么所有 0 连续段的个数是 O(\dfrac{n^2}{k}) 的，那么所有 0 连续段长度之和是 O(\dfrac{n^3}{k}) 的（这个结论我也不知道对不对，但是跑个程序模拟后发现当有一个 \frac{1}{6} 的常数的时候拟合的很好？），所以最终复杂度就是常数极小的 O(\dfrac{n^3}{k})，我随了 10^3 组数据，大概在 9\times 10^7 范围，并且没有大于 9.2\times 10^7 的数据，所以能过。