配点 : 700 点
問題文
正整数 N,M 和素数 P 和 (1,2,\dots ,N) 的排列 对于 Y=(Y_1,Y_2,\dots ,Y_N) 。
(1,2,\dots ,N) 的排列 对于 X=(X_1,X_2,\dots ,X_N) , 定义f(X) 如下。 小于或等于
- 2 以上 N 的整数 k 的以下值 B_k 什么时候 \max(B_2,B_3,\dots ,B_N)
- 坐标是 (X_1,Y_1), (X_2,Y_2), \dots ,(X_k,Y_k) 维度平面上的 2 一组 k 点 S 的边界框面积为 除以 M 时的余数 使得
f(X) 是最小值 X 的数量 除以 P 求余数。 您将获得
T 测试用例,因此请找到每个测试用例的答案。
什么是边界框?
S 的边界框是 包含 S 内部或圆周上的所有点,并且 x 边平行于面积最小的轴的矩形。制約
- 1 \le T \le 100
- 2 \le N \le 3000
- 1 \le M \le 10^7
- 10^4 \le P \le 10^9
- P 是素数
- Y 满足 (1,2, \dots ,N) 的排列 对于
- 在所有测试用例中 N 的总和是 3000 以下
- 所有输入值均为整数
入力
输入将以以下形式从标准输入给出。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出。 对于第
N M P Y_1 Y_2 \ldots Y_N
出力
T 行。
i 行中, i 个测试用例, 打印除以f(X) 是最小值 X 的数量 除以 P 后的余数。
入力例 1
4 4 6 998244353 2 3 4 1 13 1 10007 1 10 6 5 13 12 8 11 9 2 7 3 4 2 10000000 999999937 1 2 24 101 20250101 13 18 12 8 16 11 2 10 9 4 6 23 22 14 3 17 7 19 1 21 5 15 24 20
出力例 1
12 4938 2 888752
1 对于第二个测试用例,例如 X=(3,1,4,2) 保证可以在 (B_2,B_3,B_4)=(2,0,3) 这是 f(X)=3 。f(X) 的最小值为 3 和f(X)=3 有 X 满足 12 。
2 对于第二个测试用例,所有 关于 X 关于 f(X)=0 答案是 这是除以 13! 输出为 P=10007 后的余数。