2.6 KiB
2.6 KiB
CF2205E Simons and Dividing the Rhythm
题目描述
我紧握手中的烦恼，然后将它们抛向千里之外。
—— SHUN，《ONMYWAY》
假设 Simons 有一个长度为 m 的数组 $a$。
Simons 需要对该数组执行如下操作，且仅能执行一次：
- 首先，他需要选择一个整数 $k$，并选定
k对整数 $[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$，使得：- 对每个 $1\le i\le k$，都有 $l_i\le r_i$；
- $l_1=1$，$r_k=m$；
- 对每个 $i$（$1 \leq i < k$），$r_i+1=l_{i+1}$。
- 然后，他分别将每个子数组
[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 执行如上的一次操作后，可以变换为 $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 取模。
输入输出样例 #1
输入 #1
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
输出 #1
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]$。
由 ChatGPT 5 翻译