#P17540. 发迹
发迹
背景
:::epigraph[——《发迹》]
我种的种子从来没结果
我把自己关在家里
想要给自己点空间
:::
题目描述
定义一个包含 种类型元素的序列 (下标从 开始)的一个重排的权值为其最长的满足如下条件的子区间 的长度:
- 。
- 。
特别地,如果没有满足条件的子区间,则重排的权值为 。
Barry 有一个长度为 的序列 ,求序列 的所有重排中,权值最小的重排数量对 取模的值。两个重排不同,当且仅当存在一个位置上两个重排中元素的类型不同。
显然,序列初始的元素顺序对答案没有影响。所以为了减小输入量,我们将给你一个长度为 的序列 , 表示序列中 类型元素出现的次数,而上述问题中的 。
输入格式
本题包含多组测试。
第一行一个整数 ,表示测试数据组数。对于每组测试数据:
第一行一个整数 ,意义如题目所示。
接下来 个用空格隔开的整数,表示出现次数序列 。
输出格式
输出 行,每行一个整数,表示对应测试数据的答案。
3
1
5
3
2 3 2
10
1 2 3 4 5 6 7 8 9 10
1
148
648341419
提示
数据范围
本题开启捆绑测试。
对于 的测试数据,,,,。
| 子任务 | 得分 | ||
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 | |||
| 7 | |||
后记
:::epigraph[——《发迹》]
真的 有数不清的遗憾
但现在看来觉得没什么
那天我流了很多泪
在那之后我告诉自己就不再轻易 cry
:::