AT_abc378_g [ABC378G] Everlasting LIDS

[problemUrl]: https://atcoder.jp/contests/abc378/tasks/abc378_g 整数 $ A,B,M $ が与えられます。 $ (1,2,\ldots,AB-1) $ の順列 $ P=(P_1,\ldots,P_{AB-1}) $ であって、以下の条件を全て満たすものは何通りありますか？個数を $ M $ で割ったあまりを求めてください。 - $ P $ の最長増加部分列の長さは $ A $ - $ P $ の最長減少部分列の長さは $ B $ - 整数 $ n $ であって、$ P $ の末尾に $ n+0.5 $ を追加しても最長増加部分列の長さも最長減少部分列の長さも変化しないようなものが存在する

N/A

N/A

### 制約 - 入力される数値は全て整数 - $ 2\leq\ A,B $ - $ AB\leq\ 120 $ - $ 10^8\leq\ M\leq\ 10^9 $ - $ M $ は素数 ### Sample Explanation 1 例えば、$ P=(2,4,5,1,3) $ は条件を満たします。これは以下のようにして確認できます。 - $ P $ の最長増加部分列の長さは $ 3 $ - $ P $ の最長減少部分列の長さは $ 2 $ - $ n=4 $ とすると、$ (2,4,5,1,3,4.5) $ の最長増加部分列の長さは $ 3 $ かつ最長減少部分列の長さは $ 2 $ 条件を満たす $ (1,2,3,4,5) $ の順列は $ 10 $ 通りです。 ### Sample Explanation 2 個数を $ M $ で割ったあまりを出力してください。