2026 杭电暑期多校 8-1010-合并之后字典序就变小了 · znzryb
# 题目大意
### 合并之后字典序就变小了
**时间限制**:2000 / 1000 MS(Java / 其他)
**内存限制**:524288 / 524288 KB
<!-- Notion block type: heading_4 -->
给定一个长度为 $N$ 的数组 $A$,其中每个元素均属于 $\{0,1,2\}$。
你可以执行任意多次以下操作:
> 选择两个相邻元素 $A_i, A_{i+1}$,将它们删除,并在原位置插入 $(A_i + A_{i+1}) \bmod 3$。
每次操作会使数组长度减少 $1$。
定义 $f(A)$ 为通过若干次(可以是 $0$ 次)操作能够得到的**字典序最小**的数组。
对于数组 $B$,定义
$$
\operatorname{val}(B)=\sum_{i=1}^{|B|} B_i \cdot 3^{\,i-1}
$$
给定数组 $A$,求
$$
\sum_{L=1}^{N}\sum_{R=L}^{N}\operatorname{val}\bigl(f(A[L,R])\bigr)
$$
对 $998244353$ 取模后的结果。其中 $A[L,R]$ 表示子数组 $[A_L, A_{L+1}, \ldots, A_R]$。
<!-- Notion block type: heading_4 -->
对于两个不同的数组 $P, Q$,若满足以下任意一条,则称 $P$ 的字典序小于 $Q$:
- $P$ 是 $Q$ 的前缀;
- 存在位置 $i$,满足 $P_i < Q_i$,且对所有 $j < i$ 都有 $P_j = Q_j$。
<!-- Notion block type: heading_4 -->
第一行一个整数 $T$,表示测试数据组数。
对于每组测试数据:
- 第一行一个整数 $N$;
- 第二行 $N$ 个整数 $A_1, A_2, \ldots, A_N$。
数据范围:
- $1 \le N \le 2 \times 10^5$;
- $0 \le A_i \le 2$。
OJ 中只有一个正式测试点,该测试点满足 $T = 10000$,$\sum N = 2 \times 10^6$。
<!-- Notion block type: heading_4 -->
对于每组测试数据输出一行,表示所有子数组对应的 $\operatorname{val}(f(A[L,R]))$ 之和对 $998244353$ 取模后的结果。
<!-- Notion block type: heading_4 -->
```
3
2
2 1
3
1 1 2
4
2 1 0 2
```
<!-- Notion block type: heading_4 -->
```
3
9
30
```
<!-- Notion block type: heading_4 -->
**第一组数据**:$A = [2, 1]$,共 $3$ 个子数组。
| 子数组 | $f$ | $\operatorname{val}$ |
| --- | --- | --- |
| $[2]$ | $[2]$ | $2$ |
| $[1]$ | $[1]$ | $1$ |
| $[2,1]$ | $[0]$ | $0$ |
其中 $[2,1]$ 合并后得到 $[(2+1)\bmod 3] = [0]$,字典序小于 $[2,1]$。总和为 $2+1+0=3$。
**第二组数据**:$A = [1,1,2]$,共 $6$ 个子数组。
| 子数组 | $f$ | $\operatorname{val}$ |
| --- | --- | --- |
| $[1]$ | $[1]$ | $1$ |
| $[1]$ | $[1]$ | $1$ |
| $[2]$ | $[2]$ | $2$ |
| $[1,1]$ | $[1,1]$ | $4$ |
| $[1,2]$ | $[0]$ | $0$ |
| $[1,1,2]$ | $[1]$ | $1$ |
其中 $[1,1]$ 若合并会得到 $[2]$,字典序反而更大,故不操作;$[1,1,2]$ 可以一路合并为 $[1]$,它是所有可达数组中字典序最小的。总和为 $1+1+2+4+0+1=9$。
**第三组数据**:$A = [2,1,0,2]$,共 $10$ 个子数组,$\operatorname{val}$ 依次为
$$
2,\;1,\;0,\;2,\;0,\;1,\;6,\;0,\;0,\;18
$$
总和为 $30$。例如整个数组 $[2,1,0,2]$ 的字典序最小结果为 $[0,0,2]$,其 $\operatorname{val} = 0 + 0\cdot 3 + 2\cdot 9 = 18$。
# 思路讲解
队友赛时过了,我就不看了。
# AC代码
::: 源代码
```cpp
```
:::
# 心路历程(WA,TLE,MLE……)