注:\color{orange} \sqrt{} 代表会了没写,\color{red} \times 代表不会。

abc150E \color{orange} \sqrt{}

给出长度为 N 的序列 C

定义两个不同的,长度均为 n01 序列 A, B 的权值 f(A, B) 为进行以下操作的最小代价和,使得 A = B

  • 对于 i \in [1, n],若 A_i \neq B_i,则可花 D \times C_i 的代价 flip A_i。其中 D 表示在操作前有多少个 j 满足 A_j \neq B_j

易知共有 2^N \times (2^{N} - 1) 个不同的有序对 A, B。计算所有对的权值和。

N \leq 2\times 10^5


考虑一对 A, B,操作使得相同的最小代价显然是贪心地操作。具体而言:

把所有不同位按 C 升序排序。优先翻转更小的 C 更优。

把每位的贡献拆出来,令 S_i 表示 C 中有多少个数比 C_i 大。特别的,对于相等的数我们按照某种方式调整使得 \nexists i, j 满足 S_i = S_j

那么第 x 位的贡献就是:

C_x \times 4^{n - S_x - 1}\times 2^{S_x + 1} \times \sum_{i = 0}^{S_x} \binom{S_x}{i} \times (i + 1)

意义:比 C_x 小的数不会影响结果,所以先拿到外面。然后枚举有多少个比 S_x 里的位有多少个不同。拿组合数选一下然后乘一下方案。

后面的 i + 1 有点烦,把 1 拿掉,变成:

C_x \times 4^{n - S_x - 1}\times 2^{S_x + 1} \times [ (\sum_{i = 0}^{S_x} \binom{S_x}{i} \times i) + 2^{S_x}]

考虑咋算 \displaystyle \sum_{i = 0}^{S_x} \binom{S_x}{i} \times i

打开

\begin{aligned} \sum_{i = 0}^{S_x} \binom{S_x}{i} \times i &= \sum_{i = 0}^{S_x} \dfrac{S_x!}{i!(S_x - i)!} \times i \\ &= \sum_{i = 0}^{S_x} \dfrac{S_x!}{(i - 1)!(S_x - i)!} \\ &= S_x \sum_{i = 0}^{S_x} \dfrac{(S_x - 1)!}{(i - 1)!(S_x - i)!} \\ &= S_x \sum_{i = 0}^{S_x} \binom{S_x - 1}{i - 1} \\ &= S_x\times 2^{S_x} \end{aligned}

所以最后的答案是

\sum_{x = 1}^n C_x \times 4^{n - S_x - 1}\times 2^{S_x + 1} \times(S_x + 1) \times 2^{S_x}

时间复杂度 O(n)

\sum_{x = 1}^n C_x \times 2^{2n - 1}\times(S_x + 1)

草式子假了,再见。