题目大意

时间限制：2000 / 1000 MS（Java / 其他）
内存限制：524288 / 524288 KB

给定一个长度为 $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]$ 。

对于两个不同的数组 $P, Q$ ，若满足以下任意一条，则称 $P$ 的字典序小于 $Q$ ：

第一行一个整数 $T$ ，表示测试数据组数。

对于每组测试数据：

数据范围：

OJ 中只有一个正式测试点，该测试点满足 $T = 10000$ ， $\sum N = 2 \times 10^6$ 。

对于每组测试数据输出一行，表示所有子数组对应的 $\operatorname{val}(f(A[L,R]))$ 之和对 $998244353$ 取模后的结果。

1
2
3

3
9
30

第一组数据： $A = [2, 1]$ ，共 $3$ 个子数组。

其中 $[2,1]$ 合并后得到 $[(2+1)\bmod 3] = [0]$ ，字典序小于 $[2,1]$ 。总和为 $2+1+0=3$ 。

第二组数据： $A = [1,1,2]$ ，共 $6$ 个子数组。

其中 $[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$ 。

Znzryb's Blog