問題一覧 > 通常問題

No.2932 えっえっ嘘嘘嘘待って待って待って???えマジで?ほんとに?マジでやばすぎなんだけど?えっおっほんとにこんなにDPしちゃっていいんですかい???マジでやばすぎなんだけど???

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 45
作問者 : tnodinotnodino / テスター : hirayuu_ychirayuu_yc loop0919loop0919 mymelochanmymelochan kusirakusirakusirakusira amesyuamesyu nouka28nouka28 Nyaa UruzuNyaa Uruzu
0 ProblemId : 11238 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-12 07:28:46

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。