← 返回题目列表

Codeforces · 2077/E

E. 另一个折叠条

中文机器翻译题面 查看原题

对于长度为 $$$m$$$ 的数组 $$$b$$$,定义 $$$f(b)$$$ 如下。

考虑一个 $$$1 \times m$$$ 条带,其中所有单元格最初都有黑暗 $$$0$$$。您希望将其转换为一条条带,其中第 $$$i$$$ 位置的颜色具有深色 $$$b_i$$$。您可以执行以下操作,该操作分为两个步骤:

  1. 在两个单元格之间的任意线上折叠纸张。您可以根据需要弃牌多次,也可以选择根本不弃牌。
  2. 选择 一 位置滴下黑色染料。染料从顶部渗透并流到底部,将其路径上所有细胞的黑暗度增加 $$$1$$$。滴下染料后,展开条带。

令 $$$f(b)$$$ 为实现所需配置所需的最少操作数。可以证明,在有限次数的操作中总能实现目标。

给你一个长度为 $$$n$$$ 的数组 $$$a$$$。评价

$$\sum_{l=1}^n\sum_{r=l}^n f(a_l a_{l+1} \ldots a_r)$$

模 $$$998\,244\,353$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — 表示数组 $$$a$$$。

保证所有测试用例中 $$$n$$$ 的所有值的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 所需的总和模 $$$998\,244\,353$$$。

示例

输入
复制

4
3
0 1 0
6
1 0 0 1 2 1
5
2 1 2 4 3
12
76 55 12 32 11 45 9 63 88 83 32 6

输出
复制

4
28
47
7001

注意

在第一个测试用例中,

  • $$$f(a_1)=f(\mathtt{0})=0$$$
  • $$$f(a_1a_2)=f(\mathtt{01})=1$$$
  • $$$f(a_1a_2a_3)=f(\mathtt{010})=1$$$
  • $$$f(a_2)=f(\mathtt{1})=1$$$
  • $$$f(a_2a_3)=f(\mathtt{10})=1$$$
  • $$$f(a_3)=f(\mathtt{0})=0$$$

总计为 $$$0+1+1+1+1+0 = 4$$$

在第二个测试用例中,$$$f(a_1a_2a_3a_4a_5a_6) = 2$$$。这是一种可能的操作顺序。