← 返回题目列表

AtCoder · jsc2025_final_c

C. 前缀边界框、Mod、最小化

中文机器翻译题面 查看原题

配点 : 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 后的余数。