No.2932 えっえっ嘘嘘嘘待って待って待って???えマジで?ほんとに?マジでやばすぎなんだけど?えっおっほんとにこんなにDPしちゃっていいんですかい???マジでやばすぎなんだけど???
タグ : / 解いたユーザー数 45
作問者 : tnodino / テスター : hirayuu_yc loop0919 mymelochan kusirakusira amesyu nouka28 Nyaa Uruzu
問題文
$H$ 行 $W$ 列のグリッド $A$ があります、上から $i$ 番目、左から $j$ 番目のマスには整数 $A_{(i, j)}$ が書かれています。
関数 $f(A)$ を以下の問題の答えとします。
最初、マス $(1, 1)$ にいます、今いるマスから隣接した右 $(i, j+1)$ か下 $(i+1, j)$ のマスに移動することを繰り返します。
ただし、グリッドの外に出るような移動はできません。
さらに、今いるマスに書かれている値を $x$、移動先のマスに書かれている値を $y$ とすると、$x \lt y$ が成り立つ必要があります。
マス $(H, W)$ への移動方法は何通りありますか?
ここで、$2$ つの移動方法 $(P_1 \dots P_N)$ と $(Q_1 \dots Q_M)$ が異なるとは、$N \neq M$ か、$P_i \neq Q_i$ となる $i$ が $1$ つでも存在することを指します。
($P_i, Q_i$ は右か下への移動を指します。)
$H$ 行 $W$ 列、各マスに $1 \le A_{(i, j)} \le M$ の整数が書かれたグリッドは $M^{HW}$ 通りあります。
これら全てのグリッドの $f(A)$ の値の和を $998244353$ で割った余りで出力してください。
制約
- $2 \le H, W \le 2,000$
- $1 \le M \le 10^9$
- 入力は全て整数
入力
$H\ W\ M$
出力
答えを出力してください。
サンプル
サンプル1
入力
2 2 3
出力
6
$f(A) = 1$ になるグリッドは 4
通りあります。
12
12
11
13
13
33
23
23
$f(A) = 2$ になるグリッドは 1
通りあります。
12
23
それ以外のグリッドは $f(A) = 0$ です。
全てのグリッドの $f(A)$ の和は 6
になります。
サンプル2
入力
2 2 2
出力
0
どのグリッドも $(H, W)$ まで移動することができません。
サンプル3
入力
1000 1000 100000
出力
866431467
答えを $998244353$ で割った余りで出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。