AT_agc021_f [AGC021F] Trinity

[problemUrl]: https://atcoder.jp/contests/agc021/tasks/agc021_f 縦 $ N $ マス、横 $ M $ マスのマス目があります。$ i $ 行目、$ j $ 列目にあるマスを $ (i,j) $ とあらわすことにします。 特に、一番左上のマスは $ (1,1) $ と、一番右下のマスは $ (N,M) $ とあらわされます。 高橋君は $ 0 $ 個以上のいくつかのマスを黒く、他のマスを白く塗りました。 長さ $ N $ の数列 $ A $ と、長さ $ M $ の数列 $ B,C $ をそれぞれ以下のように定義するとき、列の組 $ (A,B,C) $ としてありうるものの個数を $ 998244353 $ で割った余りを求めてください。 - $ A_i(1\leq\ i\leq\ N) $ は、マス $ (i,j) $ が黒く塗られているような最小の $ j $ (存在しない場合、$ M+1 $) - $ B_i(1\leq\ i\leq\ M) $ は、マス $ (k,i) $ が黒く塗られているような最小の $ k $ (存在しない場合、$ N+1 $) - $ C_i(1\leq\ i\leq\ M) $ は、マス $ (k,i) $ が黒く塗られているような最大の $ k $ (存在しない場合、$ 0 $)

N/A

N/A

### 注意 この問題では、提出できるソースコードのサイズは $ 20000 $ B 以下に制限される。 制限を超える長さの提出は無効とするので注意すること。 ### 制約 - $ 1\ \leq\ N\ \leq\ 8000 $ - $ 1\ \leq\ M\ \leq\ 200 $ - $ N,M $ は整数である ### 部分点 - $ N\leq\ 300 $ を満たすデータセットに正解すると、$ 1500 $ 点が与えられる。 ### Sample Explanation 1 $ N=2 $ なので、$ B_i,C_i $ の情報から、各列の黒く塗られたマスの配置が一意に定まります。各 $ i $ について、$ (B_i,C_i) $ の組は $ (1,1),(1,2),(2,2),(3,0) $ の $ 4 $ 通りなので、答えは $ 4^M=64 $ 通りです。