#CW29. 前缀归位(prefixsort)

前缀归位(prefixsort)

题目描述

小 W 有一个 11 到 nn 的排列 AA。他从左到右执行插入排序,但最多只处理前 kk 个位置。

令 K=min⁡(n,k)K=\min(n,k)。处理结束后,原排列的前 KK 个元素按升序排列,后面的元素不被移动。

如果一个排列的最长严格上升子序列长度至少为 n−1n-1,称它几乎有序。子序列中的元素不要求在原排列中连续。

请统计 11 到 nn 的所有排列中,有多少个排列在上述处理后变得几乎有序。答案对给定质数 qq 取模。

输入格式

第一行输入一个整数 TT,表示询问组数。

接下来 TT 行,每行输入三个整数 n,k,qn,k,q。

输出格式

对第 xx 组询问输出一行 Case #x: y,其中 xx 从 11 开始,yy 为答案对 qq 的余数。

样例 1 输入

1
3 1 100000007

样例 1 输出

Case #1: 5

样例 1 解释

K=1K=1,处理不会改变排列。11 到 33 的六个排列中,只有严格递减排列的最长严格上升子序列长度小于 22,因此答案为 55。

样例 2 输入

1
5 3 100000007

样例 2 输出

Case #1: 54

样例 2 解释

只会把原排列的前三个位置升序排列,第四、第五个位置上的元素保持原位。共有 5454 个原排列在处理后变得几乎有序。

样例 3 输入

1
50 50 998244353

样例 3 输出

Case #1: 700438304

样例 3 解释

K=n=50K=n=50,整个排列都会被排成升序,因此答案为 50! mod 998244353=70043830450!\bmod 998244353=700438304。

数据范围

对于所有测试数据,保证:

  • 1≤T≤50001 \le T \le 5000;
  • 1≤n,k≤501 \le n,k \le 50;
  • 108≤q≤10910^8 \le q \le 10^9,且 qq 为质数。
数据类别 分值 测试点 附加条件
A 10 1∼21\sim 2 n≤8n \le 8
B 15 3∼53\sim 5 k≥nk \ge n
C 20 6∼96\sim 9 k=1k=1
D 25 10∼1410\sim 14 0≤n−min⁡(n,k)≤20 \le n-\min(n,k) \le 2
E 30 15∼2015\sim 20 无额外限制