简要题意

对于三个长度为 $n$ 的 01 字符串 $s_1,s_2,s_3$，称长度为 $n$ 的 01 字符串 $t$ 是好的当且仅当 $\forall 1 \le i,j \le n, \exists k \in \{1,2,3\}, s_{k,i} = t_i, s_{k,j} = t_j$。设 $f(s_1,s_2,s_3)$ 为这样的好的串的数量。

现在我们有三个长度为 $n$ 的随机 01 字符串 $s_1,s_2,s_3$，其中 $s_i (1 \le i \le 3)$ 的第 $j (1 \le j \le n)$ 个字符有 $\frac{p_{i,j}}{9}$ 的概率为 1，$\left(1 - \frac{p_{i,j}}{9}\right)$ 的概率为 0，其中 $p_{i,j}$ 是一个 $0$ 至 $9$ 的整数。所有的随机事件是独立的。你需要求 $f(s_1,s_2,s_3)$ 的期望，对 $998244353$ 取模。

$n \le 3 \times 10^5$

解法

引理：设 $\text{maj}(a,b,c)$ 为 $a,b,c$ 中的众数；对于三个长度为 $n$ 的 01 字符串 $s_1,s_2,s_3$，设 $\text{maj}(s_1,s_2,s_3)$ 为长度为 $n$ 的字符串 $t$，其中 $t_i = \text{maj}(s_{1,i},s_{2,i},s_{3,i})$，则 $f(s_1,s_2,s_3) = |\{s_1,s_2,s_3,\text{maj}(s_1,s_2,s_3)\}|$。

我们首先说明以上四个字符串均满足题设条件。$s_1,s_2,s_3$ 满足条件是显然的。

对于 $t=\text{maj}(s_1,s_2,s_3)$，对于任意 $1 \le i < j \le n$，存在下标 $1 \le a < b \le 3$ 满足 $s_{a,i} = s_{b,i} = t_i$，又存在 $1 \le c < d \le 3$ 满足 $s_{c,j} = s_{d,j} = t_j$。根据抽屉原理 $\{a,b,c,d\}$ 中有两个数相等，对应的下标即是满足题设条件的 $k$。

接下来我们说明不存在其它字符串满足条件。当满足条件的字符串 $t$ 不等于 $\text{maj}(s_1,s_2,s_3)$ 时，设 $t_i \ne \text{maj}(s_1,s_2,s_3)_i$，则 $t_i$ 只在 $s_{1,i},s_{2,i},s_{3,i}$ 中出现恰好一次（不能不出现，否则不可能满足题设条件），不妨假设其为 $s_{1,i}$。此时取任意 $j \ne i$，根据题设条件必然有 $t_j = s_{1,j}$（因为 $k$ 必须取 $1$），因此 $t = s_1$。

进一步地，可以分类讨论得到 $|\{s_1,s_2,s_3,\text{maj}(s_1,s_2,s_3)\}| = 4 - \sum_{i=1}^3 [\text{maj}(s_1,s_2,s_3) = s_i]$：

• $f(s_1,s_2,s_3) = 4$ 时四个字符串两两不同；
• $f(s_1,s_2,s_3) = 3$ 时必然是某个 $s_i = \text{maj}(s_1,s_2,s_3)$ 的情况而不是 $s_i = s_j$ 的情况，因为 $s_i = s_j$ 会直接导致 $\text{maj}(s_1,s_2,s_3) = s_i$；
• $f(s_1,s_2,s_3) = 2$ 时必然是 $s_i = s_j = \text{maj}(s_1,s_2,s_3)$ 且剩余的字符串跟它们不同的情况；
• $f(s_1,s_2,s_3) = 1$ 时必然是四个字符串相等的情况。

由于期望的线性性，只需要计算 $\Pr[\text{maj}(s_1,s_2,s_3) = s_i]$ 即可。由于每一位的随机事件是独立的，所以直接把每一位相等的概率乘起来就行了。

复杂度 $O(n)$。

题外话

• 本题中文名“石墨烯”纯属出题人夹带私货，与题目无关，具体含义不便透露，大家不要过度解读。
• 本题原来只有 $k=0$ 这个版本作为签到，但是因为某些原因需要稍微加强难度，就变成了现在这个版本。

Description

• 给定长为 $n$ 的序列 $a, b$，每轮操作先使每对 $(a_i, b_i)$ 中较小值变为零，较大值变为它们的差，然后使 $a$ 循环右移一位。
• 操作开始前，可以先对 $a$ 进行 $k$ 次 $a_i \leftarrow a_{i-1}$（需保证 $a_i$ 恒非负），问最少几轮操作才能使 $a$ 全变为零？
• $1 \le n, \sum{n} \le 5 \times 10^5$，$1 \le a_i, b_i \le 10^9$。

$k=0$

• 考虑对于每个 $a_i$ 分别求出至少循环右移几次之后会变为零，记之为 $d_i$，则答案即为 $\max_{1≤\le i \le n}{d_i}$。
• 遇到环上问题，首先考虑断环为链（即令 $a_{i+n}=a_i,b_{i+n}=b_i$）。

• 考虑如下转化：记 $s$ 为由 $a_1$ 个左括号，$b_1$ 个右括号，$a_2$ 个左括号，$b_2$ 个右括号，……，$a_{2n}$ 个左括号，$b_{2n}$ 个右括号顺次拼接而成的括号串，则原题中的操作过程就相当于对 $s$ 进行括号匹配的过程，而 $a_i$ 会被哪个 $b_j$ 首次消成零，就取决于 $a_i$ 对应的第一个左括号所匹配的右括号属于哪个 $b_j$ 。

  • “使 $(a_i, b_i)$ 中较小值变为零，较大值变为它们的差” $\rightarrow$ “匹配 $a_i, b_i$ 对应的括号”；
  • “使 $a$ 循环右移一位” $\rightarrow$ “未被匹配的左括号继续向右寻找右括号尝试匹配”。
• 对于括号匹配问题，自然想到利用前缀和转化。
• 令 $c_i=\sum_{j=1}^{i}(a_i-b_j)$，记 $p_i$ 为最小的满足 $p_i > i$ 且 $c_{p_i} \le c_i$ 的下标，则 $d_i$ 即为 $p_i-i$。
• 使用单调栈即可求出所有 $p_i$，时间复杂度为 $O(\sum n)$。

正解

• 加入了 $k$ 的限制后，考虑二分答案 $x$，转而求在 $x$ 轮操作后将 $a$ 全变为零的最少 $-1$ 次数。
• 发现直接在断环为链的 $2n$ 个数上不太好计算贡献（因为可能会重复计算），所以我们进行如下调整：将 $a,b$ 同时循环右移若干位，使得 $a_i-b_i$ 的前缀和 $c_i$ 的最小值在 $c_n$ 处取到。
• 这样调整的好处是，对于调整后的 $a,b$，我们所关心的 $p_i(1 \le i \le n)$ 都不会超过 $n$，也就是说，在实际操作过程中，不会出现 $a_n > 0$ 右移到 $a_1$ 的情况。
• 因此，我们仅通过调整 $a, b$ 就将环上问题转化为了一个长为 $n$ 的链上问题。
• 接下来考虑如何在调整后的 $a,b$ 上计算答案为 $x$ 时的最少 $-1$ 次数。
• 不难想到对 $a$ 从 $n-x$ 到 $0$ 使用贪心，若当前位置 $i$ 对应的 $d_i=p_i-i > x$，即若 $\min_{j=i+1}^{i+x}{c_j} > c_i$，则对 $a_{i+1}$ 进行 $\min_{j=i+1}^{i+x}{c_j} - c_i$ 次 $-1$。
• 整个过程均可通过单调栈维护。
• 时间复杂度为 $O(\sum n \log k)$。

English version

Each operation transform three adjacent characters into one. If the string starts with 11, the answer should be yes since we can first transform the remaining part into a single 0 or 1 and then the value of 11? is always $1$.

If the string ends with 1, only 101 has no solution, otherwise it starts with 11 or 0, or we can transform 10? in the front of the string into a 0. Then transform the rest part of the string into a single character to make the last operation 0?(anything):1 makes 1.

If an operation transformed a string ending with 0 into one ending with 1, it must be 1?1:0 makes 1.

Consider the case where the strings contains 11 as a substring. After transforming the remaining part, ?11?? or ??11? will be derived. The cases are 01100, 00110, 01110, 10110. All other cases start with 11 or end with 1.

All cases of ??11? have a solution:

(0?0:1)?1:0 makes 1.

(0?1:1)?1:0 makes 1.

1?(0?1:1):0 makes 1.

However, 01100 has no solution.

Since 0?0:1 equals 1, before the last 1, any two adjacent 0's with no 1 in between can be eliminated. Thus, if there are two 1's with an even number of 0's in between, and there are an even number of characters in front the former 1, i.e., (..)*1(00)*1(..)*0 in regular expression, the answer should be yes, since after eliminating the 0's in between, the 1's become adjacent. The parity of the characters before the former 1 guarantees that it will not become 01100.

Another case is that the string ends with 0 and every pair of adjacent 1's has an odd number of 0's in between. Since 0(1?0:1)0 makes 000, 1(0?1:0)1 makes 101, 10(1?0:0)01 makes 10001, there is no way to change the parity of the consecutive 0's to make 11 to change the ending 0 into 1.

In the remaining case, there are even 0's between some pair of adjacent 1's, but the number of characters before the first 1 is odd, there must be only one pair. Suppose the string is 1-indexed. It is because the indices of such pair of 1's must be [odd, even]; while the indices in the previous case must be [even, odd]. Thus, if there are two such pairs of this case [odd, even], in the parity sequence [odd, even, ..., odd, even] there must be an [even, odd] as a substring.

Therefore, any other pair of adjacent 1's must have odd 0's in between, i.e., $0(00)^*\color{blue}(10(00)^*)^*\color{red}1\color{black}(00)^*\color{red}1\color{blue}((00)^*01)^*\color{black}(00)^+$ in regular expression. Any operation remains the string in this case, except that the string is $0(00)^*\color{blue}(10(00)^*)^*\color{red}1\color{red}1\color{black}(00)^+$ and the operation is $\color{red}1\color{black}?\color{red}1\color{black}:0$ makes 1. Since it must ends with `00`, it becomes a string ending with `0` and every pair of adjacent 1's has odd 0's in between, which is a case mentioned before that has no solution.

In conclusion, it has a solution if and only of at least one of the two following conditions is met:

• It ends with 1 but it is not 101.
• It has two adjacent 1's such that there are even 0's in between and the number of characters before the former 1 is even.

中文版本

英文题解里描述了做本题的一种思路，以及证明。

如果要直接写做法的话，是下面这样：

假设字符串下标从 $1$ 开始编号。

首先判断是否存在 $i,j$ 使得 $i$ 是奇数，$j$ 是偶数，$s_i$ 和 $s_j$ 都是 1，且这两个字符中间都是 0。

• 如果是，那么先把中间的 0 和 $s_j$ 写成 (0?0:0?0:.....:1)，表达式的值为 1（一定有偶数个 0），然后分三种情况：

  • 如果 $i=1$，那么就直接把 $s_j$ 后面的部分变成一个数，最后变成 (1?1:*) 是 1。

  • 否则考虑把 $s$ 的第 $1\sim i-2$ 位变成一个数，并计算出这个值。

    • 如果值为 0 那么有 ((0?*:1)?1:*) 等于 1。
    • 如果值为 1 那么有 (1?(*?1:1):*) 等于 1。

• 否则，判断是否满足字符串末尾是 1 且本身不等于 101：

  • 如果是，那么字符串一定以 0 或 10 开头，于是第一位或前三位操作后一定是 0，然后留下开头的 0 和结尾的 1，把中间的部分变成一个数，最后 (0?*:1) 结果一定是 1。
  • 否则，无解。

此外，还有一种比较特别的解法：

可以发现构造的过程中需要用到不超过两层括号（不算整个表达式最外面一层）。所以如果你要是猜到了这一点可以直接使用动态规划从右到左扫这个字符串，记录每一层栈中的内容。最多三层栈，每层栈最多两个比特，一共 $6^3+6^2+6=258$ 种状态。大概也能过。

不知道有没有什么奇怪的乱搞可以搜过去。不过我还是欢迎吧。

引言

今年命题会的时候，我们惊奇地发现今年的模拟题还没有着落。

于是我翻出了这个压箱底的 idea，当作一个中模拟。

idea 恰如其分来自在你清食堂的吃饭经历，获得了大家的一致认同。

时限只开 3s 是因为有 100 个点，开太久会更严重地卡评测的。std 跑了 1.6s。出题人试图开 5s 被系统部和赛务部的同学们拦下了

比赛情况

本题的完整版本预期难度是 medium，不过我个人认为是 easy+（？）。

丝路市西套村代表队获得了本题首杀！

本题大约有一半的队伍通过了本题。

同时，不少夺冠热门队伍在本题上获得了大量罚时。

题意简述

食堂餐桌座位分布在第一象限网格每个 $3 \times 3$ 完整格子右上角的 $2 \times 2$ 格子，剩下的部分为走廊。

每次可以从一个走廊格子走到四连通相邻格子。

每次一名顾客从最左下角的格子出发，试图找到最优的一个满足自己容忍条件的空座位。容忍条件形如桌子上坐了几人以及自己因此应该去哪里（请参考原题面）。

此外还会有部分座位突然出现或消失顾客，也即状态翻转。

输出每次顾客坐到了哪里，以及突然变化的顾客是来是去。

操作次数 $q$ 不超过 $5 \times 10^5$。第二类操作值域不超过 $10^4$ 且总是修改在餐桌处。3s/1GB。

思路

本题总体思路比较简单，这里直接给出完整版正解做法。

注意到第一类操作可能遇上的下标范围是 $O(\sqrt{q})$ 级别的，我们不妨考虑做预处理。

观察到其优先顺序是固定的，我们可以预先排序得到各个餐桌格子的优先顺序。这个排序可以通过数学方法或者 bfs 做到线性。

考虑第一类操作，我们可以用 set 或可删堆（对顶堆）存一下每个满足对应条件的位置。

第二类操作对于下标超界的部分也可以单独拿一个 set 存；没超界的部分可以和前面的部分使用同一套方法处理。

不用太多卡常，验题人开了八九个 set 都过了。std 不到 2kb。

本题非常善良，值域只开 $10^4$ 是为了方便压位（记得用 $10001$ 压）。没有特意卡 umap/bitset 之类的东西，应该是可以轻松过的。

总结

• 在这样一场毒瘤的比赛中，
• 这道题目无疑是出题人无私的馈赠，
• 经典的模型、较低的难度和不大的代码量，能帮助你把分数收入囊中
• 出题人相信，这个美妙的题目，可以给拼搏于 XCPC 的追梦之路上的你，提供一个有利的援助。

题意

求有多少个长度为 $n$ 的排列，使得 $S$ 为其长度为 $k$ 的字典序最大的子序列和其长度为 $k$ 的字典序最小的子序列的最长公共子序列之一。

题解

下文用 $T$ 代替 $S_0$，用 $R$ 代替 $S_1$。

性质一：考虑 $T$ 的形态，令 $i=\min\{i \mid i = k \lor T_i < T_{i+1}\}$，则 $T_1, T_2, \cdots, T_i$ 为 $p$ 字典序最大子序列长度为 $i$ 的前缀，$T_{i+1}, \cdots, T_k$ 为 $p$ 的长度为 $k - i$ 的后缀。

下称 $T_1, \cdots, T_i$ 为 $T$ 的头部，$T_{i+1}, \cdots, T_k$ 为 $T$ 的尾部。可以用类似的方式定义 $R$ 的头部与尾部。

容易发现 $S$ 唯一。考虑 $S$ 的形态。不妨令 $T$ 的尾部长度 $< R$ 的尾部长度。则 $T$ 的尾部一定是 $S$ 的一段后缀。删除这段后缀后，令 $R$ 尾部的剩下部分为 $p_l, \cdots, p_r$。则此时 $S$ 的一段后缀为有序集合 $\{p_i \mid i \in [l, r] \land p_i \in T \}$。删除这段后缀后，剩下的部分为两个头部的最长公共子序列。由于两个头部都是单调，因此 $S$ 剩下部分的长度至多为 $1$。

接下来可以考虑分类讨论开始 dp 计数了。

1. $S_1$ 为 $T, R$ 头部的一部分。

   对于 $S_1$ 前面的部分，我们要计数的问题是：有多少个长度为 $i$ 的排列，其字典序最大子序列的长度为 $j_1$，字典序最小子序列的长度为 $j_2$，且它们的最后一位一定是 $k$。发现 $\le k$ 的部分与 $\ge k$ 的部分是独立的，只需要分别 $dp$ 再组合数拼起来即可。现在的问题转换为：长度为 $i$ 的排列，其字典序最大子序列长度为 $j$，其最后一位和字典序最大子序列的最后一位为 $k$。这个容易用 $\Theta(n^3)$ 的时间复杂度 dp。

   对于 $S_1$ 后面的部分，不妨令 $S_2 < S_1$。则 $S_2$ 一定为 $R$ 的尾部。讨论 $T$ 的尾部是否比 $R$ 更长。

   1. $T$ 的尾部比 $R$ 的更长。

      则 $S_1$ 与 $S_2$ 之间必须存在数，且这些数都必须大于 $S_1$。对于 $S_2, \cdots, S_m$，其一定为原排列的一个后缀。这部分容易计数。

   2. T 的尾部比 R 的更短。

      令 $i = \min\{i \mid i = m \lor S_i < S_{i+1}\}$，则 $S_{i+1}, \cdots, S_m$ 为原排列的一个后缀。此时只需要对 $S_1$ 与 $S_i$ 之间的部分计数。此时问题转化成，有多少个长度为 $n'$ 的排列，其字典序最大子序列的长度为 $i$ 的前缀为 $S_1, \cdots, S_i$。这一部分也容易用 $\Theta(n^2)$ 或 $\Theta(n^3)$ 的时间复杂度 dp。

2. $S_1$ 为 $T, R$ 尾部的一部分。

   不妨令 $T$ 的尾部长度小于 $R$ 的尾部长度。则 $S$ 为 $T$ 的尾部。枚举 $R$ 的尾部长度与 $T$ 的尾部长度之差 $i$，再枚举 $T$ 的头部的最后一位 $p'$ 是多少。分开对 $p_1, \cdots, p'$ 和 $p', \cdots, S_1$ 计数。这两部分都可以用类似于 1 中对 $S_1$ 之前部分计数的方法计数。注意这个东西可以预处理，没有必要每枚举一次都重新计数一遍。

3. $S_1$ 为 $T$ 头部、$R$ 尾部的一部分或 $R$ 头部、$T$ 尾部的一部分。

   不妨令 $S_1$ 为 $T$ 头部、$R$ 尾部的一部分。

   $S_1$ 后面的部分与 1.2 相同。

   下面尝试对 $S_1$ 前面的部分计数。

   令 $k_2$ 为 $R$ 头部的最后一位，$k_1$ 为 $T$ 中 $S_1$ 前面的数。

   1. $S_1$ 为 $R$ 尾部的第一位。

      则 $S_1$ 的前一个数一定为 $k_1$。枚举 $k_2$，将 $\le k_2$ 的部分与 $> k_2$ 的部分使用类似于 1 中 $S_1$ 前面部分的方法分开 dp 计数。注意这个东西可以预处理，没有必要每枚举一次 $k_2$ 就重新 dp 一次。

   2. $S_1$ 不为 $R$ 尾部的第一位，且 $k_2 < S_1$。

      枚举 $k_2$，再枚举 $R$ 尾部在 $S_1$ 之前的长度，以 $k_2$ 或 $S_1$ 为界分开 dp，用上述方法仍然容易处理。

   3. $S_1$ 不为 $R$ 尾部的第一位，且 $k_2 > S_1$。

      这就要求 $k_2$ 必须在 $k_1$ 前面。注意到 $k_1$ 之后一定紧挨着 $R$ 尾部的第一位。枚举 $k_2$，再枚举 $R$ 尾部的第一位与 $S_1$ 之间有多少数，一样可以用类似的方法 dp。

总时间复杂度 $\Theta(n^3)$。

Bonus: $n \le 5000$。

瓶颈在于以下问题：有多少个长度为 $i$ 的排列，其字典序最大子序列的长度为 $j$。

设 $dp_{i,j}$ 为我们所希望求出的答案。每次尝试向已有排列中加入一个更小的数。如果这个数被放在了整个排列的最右边，则字典序最大子序列的长度会增加 $1$，否则不变。按照这个思路对 dp 式子进行转移，时间复杂度 $\Theta(n^2)$。

由于 $\Theta(n^2)$ 算法不仅要求对 dp 进行优化，还要求选手在分类讨论的过程中进行相当精细的实现，因此最终只开了 $n \le 400$ 来允许实现相对较差的算法通过。

题意简述

给定 $n$ 个非负整数 $x_1,x_2,\dots,x_n$。

对于任意 $n$ 个节点的无向连通图 $G$，将其节点由 $1$ 至 $n$ 标号，则其分数定义为 $$\text{score}(G) = \sum_{i=1}^n \sum_{j=i+1}^n \text{dist}_G(i, j)x_ix_j,$$ 其中 $\text{dist}_G(i,j)$ 表示图 $G$ 上 $i$ 到 $j$ 的最短路径长度。

你的任务是输出所有 $n$ 个节点的无向连通图中分数的最大值。

$1 \le n \le 300$，$0 \le x_i \le 2000$

解法

我们首先假设至少有两个 $x_i$ 不为 $0$，否则答案一定是 $0$。

定理 1：一定存在一棵树取到最大分数。

不是一棵树的 $G$ 删掉一条不改变连通性的边肯定会让 $\text{dist}_G(i,j)$ 变大，所以这个定理是显然的。不过只知道 $G$ 是一棵树还不足以解决本问题。

定理 2：一定存在一条链取到最大分数。

假设分数最大的 $G$ 是一棵树但不是一条链。以任一度数大于等于 $3$ 的点 $r$ 为根。不妨假设其度数为 $3$，三个子树为 $A,B,C$，子树根分别 $a,b,c$，子树的 $x$ 的和分别为 $x_A,x_B,x_C$。假设 $x_A \le x_B \le x_C$。

考察如下调整：删去 $(r,b)$ 加上 $(a,b)$。此时从 $C$ 和 $r$ 到达 $B$ 的距离增加 $1$（多经过 $a$），从 $A$ 到达 $B$ 的距离减少 $1$（少经过 $r$），其他距离均不变。

因此图的分数变化为 $(x_r+x_C-x_A)x_B$。当这个值大于 $0$ 的时候，我们就可以得到一个分数更大的方案，矛盾。

若 $(x_r+x_C-x_A)x_B = 0$，有两种情况：

• $x_B = 0$，此时子树 $B$ 里的所有点 $p$ 都有 $x_p = 0$。将这些点插入到任意两个 $x$ 不为 $0$ 的点 $a, b$ 的路径中（注意我们假设了至少有两个 $x$ 不为 0），这样一定会让分数变大。
• $x_A=x_B=x_C$ 且 $x_r=0$。此时我们尝试进行调整以最大化第二个目标 $\text{score}^\star(G) = \sum_i \sum_{j > i} \text{dist}_G(i,j)$。注意到这个就是所有 $x$ 都是 $1$ 的版本所以一定可以进行调整，而这样调整一定不改变 $\text{score}(G)$。

因此每次调整要么会提升 $\text{score}(G)$，要么 $\text{score}(G)$ 不变的同时 $\text{score}^\star(G)$ 增加，而两者均为正整数且有上界。故不断进行调整后必然到达一个 $(\text{score}(G), \text{score}^\star(G))$ 的局部最大值，此时无法进行以上调整，也就是不存在度数大于等于 $3$ 的点。证毕。

运用以上定理，我们此时的任务是把 $x$ 重排为 $x'$，最大化 $\sum_i \sum_{j>i} (j-i)x_ix_j$。

我们还需要以下有关这个问题的解的性质。

定理 3：一定存在一个单谷的重排 $x^\star$ 达到最大分数。

不妨假设 $x$ 两两不同且大于 $0$，这可以通过给每个数加上一些微小扰动完成。

若最优的重排 $x^\star$ 不是单谷的，则存在 $p$ 满足 $x^\star_{p-1} < x^\star_p>x^\star_{p+1}$。考虑两种调整：

• $\text{swap}(x^\star_{p-1},x^\star_p)$，分数增加 $(x^\star_p - x^\star_{p-1})(x_{p+1 \sim n} - x_{1 \sim p-2})$；
• $\text{swap}(x^\star_{p+1},x^\star_p)$，分数增加 $(x^\star_p - x^\star_{p+1})(x_{1 \sim p-1} - x_{p+2 \sim n})$

注意到两个增量的第一项都是正的，而两个第二项的和为 $x_{p-1}+x_{p+1}$ 也是正的，因此必然存在一个调整增大分数。证毕。

最后我们把分数式子稍微变换一下。

$$\begin{align*} \sum_i \sum_{j>i} (j-i)x_ix_j & = \sum_i \sum_{j>i} \sum_{k=i}^{j-1} x_ix_j \\ = & \sum_k \sum_{i \le k} \sum_{j > k} x_ix_j \\ = & \sum_k x_{1 \sim k} \times x_{k+1\sim n}, \end{align*}$$

也就是说分数等于每个位置的前缀和和后缀和的乘积的和。

由于最优解是单谷的，考虑从大到小依次加入每个 $x_i$，此时每个 $x_i$ 一定加在未加入的部分的第一个或最后一个。加入进去之后，可以确定一个前缀和（加在后面是确定后缀和，其实也就是确定了剩余位置的前缀和），也就确定了分数中一项的贡献。

因为分数只关心每个位置的前缀和是多少，依此设计 DP：设 $f_{i,j}$ 表示加入了前 $i$ 大数，加在前面的所有数的和为 $j$ 时分数的最大值。加在后面的数的和可以直接通过 $i$ 和 $j$ 推导出来。转移枚举第 $i+1$ 大数放在前面还是后面，加上对应项的贡献即可。

复杂度 $O(n^2 \max x_i)$。