C - Prefix Bounding Box, Mod, Minimize Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 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 で割った余りとなります。