#CW29. 前缀归位(prefixsort)
前缀归位(prefixsort)
题目描述
小 W 有一个 到 的排列 。他从左到右执行插入排序,但最多只处理前 个位置。
令 。处理结束后,原排列的前 个元素按升序排列,后面的元素不被移动。
如果一个排列的最长严格上升子序列长度至少为 ,称它几乎有序。子序列中的元素不要求在原排列中连续。
请统计 到 的所有排列中,有多少个排列在上述处理后变得几乎有序。答案对给定质数 取模。
输入格式
第一行输入一个整数 ,表示询问组数。
接下来 行,每行输入三个整数 。
输出格式
对第 组询问输出一行 Case #x: y,其中 从 开始, 为答案对 的余数。
样例 1 输入
1
3 1 100000007
样例 1 输出
Case #1: 5
样例 1 解释
,处理不会改变排列。 到 的六个排列中,只有严格递减排列的最长严格上升子序列长度小于 ,因此答案为 。
样例 2 输入
1
5 3 100000007
样例 2 输出
Case #1: 54
样例 2 解释
只会把原排列的前三个位置升序排列,第四、第五个位置上的元素保持原位。共有 个原排列在处理后变得几乎有序。
样例 3 输入
1
50 50 998244353
样例 3 输出
Case #1: 700438304
样例 3 解释
,整个排列都会被排成升序,因此答案为 。
数据范围
对于所有测试数据,保证:
- ;
- ;
- ,且 为质数。
| 数据类别 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| A | 10 | ||
| B | 15 | ||
| C | 20 | ||
| D | 25 | ||
| E | 30 | 无额外限制 |