← 返回题目列表

Codeforces · 2205/E

E. 西蒙斯和划分节奏

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

我把烦恼握在手中,然后将它们从一千个土地上扔掉。
— 顺, ONMYWAY

考虑给 Simons 一个大小为 $$$m$$$ 的数组 $$$a$$$。

Simons 必须对数组进行操作 正好一次 如下:

  • 首先,他必须选择一个整数 $$$k$$$ 并选择 $$$k$$$ 整数对 $$$[l_1,r_1],[l_2,r_2],\ldots,[l_k,r_k]$$$,这样:
    • $$$l_i\le r_i$$$ 对于每个 $$$1\le i\le k$$$,
    • $$$l_1=1$$$,$$$r_k=m$$$,并且
    • $$$r_i+1=l_{i+1}$$$ 对于从 $$$1$$$ 到 $$$k-1$$$ 的每个 $$$i$$$。
  • 然后,他独立地反转每个子数组$$$[a_{l_i},a_{l_i+1},\ldots, a_{r_i}]$$$。此后,数组将变为 $$$[a_{r_1},a_{r_1-1},\ldots,a_{l_1},a_{r_2},\ldots,a_{l_{k-1}},a_{r_{k}},a_{r_k-1},\ldots,a_{l_k}]$$$。

给你一个大小为 $$$n$$$ 的数组 $$$T$$$。计算数组 $$$S$$$ 的数量,以便 Simons 可以将 $$$S$$$ 转换为 $$$T$$$,模 $$$998\,244\,353$$$。

输入

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

第一行包含一个整数 $$$n$$$ ($$$1\le n\le 8000$$$) — $$$T$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$T_1,T_2,\ldots,T_n$$$ ($$$1\le T_i\le 8000$$$) — $$$T$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$8000$$$。

输出

对于每个测试用例,输出一个整数 - 数组 $$$S$$$ 的数量,以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

5
4
1 1 2 1
4
1 2 3 1
6
1 3 2 3 3 2
10
2 3 1 4 3 1 4 3 1 2
1
8000

输出
复制

4
7
22
383
1

注意

在第一个测试用例中,我们可以看到只有以下数组可以转换为$$$T$$$:

  • 对于 $$$S=[2,1,1,1]$$$,Simons 将选择 $$$[1,3]$$$ 和 $$$[4,4]$$$。因此,该数组将变为$$$[1,1,2,1]$$$,等于$$$T$$$。
  • 对于 $$$S=[1,2,1,1]$$$,Simons 将选择 $$$[1,4]$$$。
  • 对于 $$$S=[1,1,2,1]$$$,Simons 将选择 $$$[1,2]$$$、$$$[3,3]$$$ 和 $$$[4,4]$$$。
  • 对于 $$$S=[1,1,1,2]$$$,Simons 将选择 $$$[1,2]$$$ 和 $$$[3,4]$$$。

在第二个测试用例中,我们可以看到只有以下数组可以转换为$$$T$$$:

  • 对于 $$$S=[1,1,3,2]$$$,Simons 将选择 $$$[1,1]$$$ 和 $$$[2,4]$$$。
  • 对于 $$$S=[1,2,1,3]$$$,Simons 将选择 $$$[1,1]$$$、$$$[2,2]$$$ 和 $$$[3,4]$$$。
  • 对于 $$$S=[1,2,3,1]$$$,Simons 将选择 $$$[1,1]$$$、$$$[2,2]$$$、$$$[3,3]$$$ 和 $$$[4,4]$$$。
  • 对于 $$$S=[1,3,2,1]$$$,Simons 将选择 $$$[1,4]$$$。
  • 对于 $$$S=[2,1,1,3]$$$,Simons 将选择 $$$[1,2]$$$ 和 $$$[3,4]$$$。
  • 对于 $$$S=[2,1,3,1]$$$,Simons 将选择 $$$[1,2]$$$、$$$[3,3]$$$ 和 $$$[4,4]$$$。
  • 对于 $$$S=[3,2,1,1]$$$,Simons 将选择 $$$[1,3]$$$ 和 $$$[4,4]$$$。