#CW54. 节奏重组(rhythm)

节奏重组(rhythm)

题目描述

给定长度为 nn 的数组 TT。数组 SS 可以通过如下操作变为 TT:先把 SS 划分成若干个连续且非空的区间,再分别翻转每个区间。请统计满足条件的数组 SS 数量,答案对 998244353998244353 取模。

等价地,若把 TT 划分为区间 [l1,r1],[l2,r2],…,[lk,rk][l_1,r_1],[l_2,r_2],\dots,[l_k,r_k],则对应的 SS 为各段 Tri,Tri−1,…,TliT_{r_i},T_{r_i-1},\dots,T_{l_i} 的连接。不同划分得到相同数组时只计一次。

输入格式

从 rhythm.in 文件读入数据。

第一行包含测试用例数 tt。每组测试用例第一行包含长度 nn,第二行包含 nn 个整数 T1,T2,…,TnT_1,T_2,\dots,T_n。

输出格式

输出到 rhythm.out 文件。

对于每组测试用例输出一个整数,即满足条件的数组 SS 数量对 998244353998244353 的余数。

样例 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

数据范围

满足 1≤t≤80001 \le t \le 8000,1≤n≤80001 \le n \le 8000,1≤Ti≤80001 \le T_i \le 8000,且所有测试用例的 nn 之和不超过 80008000。

正式数据有 2020 个独立计分点,每点 55 分;一个测试点通过即得该点分数。

子任务 分值 测试点 附加条件
1 25 1∼51\sim 5(每点 5 分) 每组数据满足 n≤20n \le 20
2 6∼106\sim 10(每点 5 分) 每组数据满足 n≤200n \le 200
3 11∼1511\sim 15(每点 5 分) 每组数据满足 n≤2000n \le 2000
4 16∼2016\sim 20(每点 5 分) 无额外限制