#CW54. 节奏重组(rhythm)
节奏重组(rhythm)
题目描述
给定长度为 的数组 。数组 可以通过如下操作变为 :先把 划分成若干个连续且非空的区间,再分别翻转每个区间。请统计满足条件的数组 数量,答案对 取模。
等价地,若把 划分为区间 ,则对应的 为各段 的连接。不同划分得到相同数组时只计一次。
输入格式
从 rhythm.in 文件读入数据。
第一行包含测试用例数 。每组测试用例第一行包含长度 ,第二行包含 个整数 。
输出格式
输出到 rhythm.out 文件。
对于每组测试用例输出一个整数,即满足条件的数组 数量对 的余数。
样例 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 | 25 | (每点 5 分) | 每组数据满足 |
| 2 | (每点 5 分) | 每组数据满足 | |
| 3 | (每点 5 分) | 每组数据满足 | |
| 4 | (每点 5 分) | 无额外限制 |