【⭐】2025 ICPC 网络赛二 D

对给定子序列暴力计算权值的方法十分显然：每次删去最大元素。

我们首先尝试模拟上面的过程来导出某长为 $n$ （$n\ge 2$）的弱递减序列 $a_1,a_2,\cdots ,a_n$ 的权值表达式：

• 首先删去 $a_1$，其余 $(n-1)$ 个元素均增加 $a_1$。
• 然后删去 $(a_1+a_2)$，其余 $(n-2)$ 个元素均增加 $(a_1+a_2)$。
• 然后删去 $(2a_1+a_2+a_3)$，其余 $(n-3)$ 个元素均增加 $(2a_1+a_2+a_3)$。
• 以此类推，可以得到当将要删去第 $i$（$1\le i\le n-1$）个元素时，其值此时为 $a_i^{\prime }=a_i+\sum _{k=1}^{i-1}{2}^{i-1-k}{a}_k$，因此序列的权值为：

$$\begin{array}{rl}F& =a_n+\sum _{i=1}^{n-1}{a}_i^{\prime }\\ & =a_n+\sum _{i=1}^{n-1}(a_i+\sum _{j=1}^{i-1}{2}^{i-1-j}{a}_j)\\ & =\sum _{i=1}^n{a}_i+\sum _{i=1}^{n-1}\sum _{j=1}^{i-1}{2}^{i-1-j}{a}_j\end{array}$$

考虑交换后面的二重求和的求和顺序，分析两个变量交换后的取值范围，得到 $j\in [1,n-2]$，$i\in [j+1,n-1]$，依据 二重求和交换顺序的定理，有

$$\begin{array}{rl}F& =\sum _{i=1}^n{a}_i+\sum _{j=1}^{n-2}\sum _{i=j+1}^{n-1}{2}^{i-1-j}{a}_j\\ & =\sum _{i=1}^n{a}_i+\sum _{j=1}^{n-2}{a}_j\sum _{k=0}^{n-2-j}{2}^k\\ & =\sum _{i=1}^n{a}_i+\sum _{j=1}^{n-2}(2^{n-1-j}-1)a_j\\ & =a_n+\sum _{i=1}^{n-1}{2}^{n-1-i}{a}_i\end{array}$$

由此我们得出了对于一个给定的子序列 $a_1,a_2,\cdots ,a_n$，将其由小到大排序后各个元素在权重中的系数 $C_i$ 形如 $1,1,2,4,\cdots ,2^{n-2}$。

我们接下来希望考察将整个序列也由小到大排序后，其中某个元素 $a_i$ 在其出现的所有子段中所在的排名，设其在子段中的排名为 $k$：

• 考虑比它小的 $i-1$ 个元素，我们需要从中选出 $k-1$ 个使得 $a_i$ 的排名为 $k$，共有 $(\genfrac{}{}{0ex}{}{i-1}{k-1})$ 种方案。
• 考虑比它大的 $n-i$ 个元素，这些元素选择与否与 $a_i$ 的排名无关，故共有 $2^{n-i}$ 种方案。

依据乘法原理，我们得到每个元素在最终答案中的系数为

$$\begin{array}{rl}{C}_i^{\prime }& =\sum _{k=1}^{i-1}(\genfrac{}{}{0ex}{}{i-1}{k-1})2^{n-i}{C}_k\\ & =2^{n-i}(1+\sum _{k=1}^{i-1}(\genfrac{}{}{0ex}{}{i-1}{k})2^{k-1})\\ & =2^{n-i-1}(1+\sum _{k=0}^{i-1}(\genfrac{}{}{0ex}{}{i-1}{k})2^k)\\ & =2^{n-i}{\displaystyle \frac{1+3^{i-1}}{2}}\end{array}$$

注意式中的除 $2$ 在实现时要乘上 $2^{-1}$。此式可以在 $\mathrm{\Theta }(\log i)$ 的时间内通过快速幂快速求出。最终答案即为 $\sum _{i=1}^n{C}_i^{\prime }{a}_i$。