CF1753

成功因为虚拟机炸了，重新写一遍此文。

~~都是没有保存的错~~。

A. Make Nonzero Sum

由于 Note that it is not required to minimize the number of segments in the partition.。考虑每一段最小化……

可以发现，每一段都可以划分为长度为 1 或 2 的段。于是考虑影响。

只有长度为 2 的段会改变正负，不妨令 \(C_+, C_-\) 分别表示 1 和 -1 的个数，并假定 1 更多。

不难发现，只需要 \(\frac {|C_+ - C_-|}2\) 个长度为 2 的即可。

如果不是整数，那么直接判不可以即可。

由于有影响，考虑 DP。

设 \(f_i\) 表示考虑前 \(i\) 个数，最多能够放多少个长度为 2 的。

于是有

\[f_i = \max \begin{cases} f_{i - 1} \\ f_{i - 2} + 1 &, a_i = 1 \end{cases} \]

考虑在 DP 变化的地方放置长度为 2 的即可。

当时脑子抽了，用了两种合并的方法。

详见：https://codeforces.com/contest/1753/submission/211561532

但是实际上只需要通过 \(x! = x \times (x -1)!\) 合成即可（2048……

假定有 \(C_0\) 个 \(0\)，并且在前 \(C_0\) 个数中有 \(k\) 个 1。

那么考虑此时一个有效的操作，即是在前 \(C_0\) 中选择到了一个 \(1\)，在后面中选择了一个 \(0\)。

有效的概率为

\[P_k = \cfrac {k^2}{n \choose 2} \]

于是考虑状态转移，设 \(f_k\) 表示从前 \(C_0\) 个数中有 \(k\) 个 \(1\) 的状态转移到 \(0\) 个 \(1\) 的期望步数。

根据 markov 中的期望线性方程求解的方法，有

\[f_k = 1 + (1 - P_k)f_k + P_k f_{k - 1} \]

稍微魔改一下，就变成了：

\[f_k = \frac {1}{P_k} + f_{k - 1} \]

于是小小递推即可。

然而我当时是反着推的，无所谓，一样的：Submission #211560140 - Codeforces

转换问题：等价于将两个 . 移动到一起的最小代价。

显然可以发现，一个障碍最多移动一次。

借用大佬的图：

于是我们可以考虑如此建图。跑一个最短路即可。

非常恶心，虽然不是顶级难度。

最优的策略一定是把乘法向后移，把加法向前移。

思考 It's guaranteed that the current value of the resulting product does not exceed 2x10^9. 的意义。

发现，除去 \(\times 1\)，最多只会有 \(\log C\) 个乘法。

于是考虑枚举其子集，为 \(2^{\log C}\)。所以需要优化。

有一个简单而优雅的剪枝：如果两个数相等，那么一定是选择最前面的。

由于 \(12! = 6227020800 \gt 2 \times 10^9\)，所以其实最多只会有 \(O(2^{12})\) 种状态。

那么在钦定了向后移动的乘法后，我们需要找到前 \(rest\) 个移动到前面贡献最大的加法。

考虑二分移动到前面的贡献 \(\Delta\)，在每一段再二分数量。

考虑如何计算每一个加法的 \(\Delta\) ？考虑加法移动前，其贡献为 \(x \times suf_x\)，移动后的贡献为 \(x \times pre_x \times suf_x\)。

其中 \(suf_x\) 和 \(pre_x\) 是指乘法移动后，\(x\) 前面的乘法前缀积和后面的乘法后缀积。

于是 \(\Delta x = x \times (pre_x - 1) \times suf_x\)。

NOTICE：

二分 \(\Delta\) 时找到最大的 \(cnt > rest\) 的那个 \(\Delta\)，由于多算了 \(cnt- rest\) 个，并且这些数的贡献一定是 \(\Delta\)，所以再减去 \((cnt - rest) \times \Delta\) 即可。
\(\Delta\) 可能很大很大，所以上界大一点（我用的倍增，所以直接是从 \(2^{60}\) 开始向下……虽然没必要）