No.1836 Max Matrix
タグ : / 解いたユーザー数 90
作問者 :
Sumitacchan
/ テスター :
👑 
hitonanode
👑 
ygussany
問題文
$H$ 行 $W$ 列の行列 $C$ であって、次の条件を全て満たすものは何通りあるでしょうか。
- $C$ の各成分 $C_{i,j}\ (1\le i\le H,1\le j\le W)$ は $1$ 以上 $M$ 以下の整数である。
- 任意の整数 $i,j\ (1\le i\le H,1\le j\le W)$ に対して $C_{i,j}=\max(a_i,b_j)$ が成り立つような、整数列の組 $a=(a_1,a_2,\dots,a_H),b=(b_1,b_2,\dots,b_W)$ が存在する。
答えは非常に大きくなることがあるので $998244353$ で割った余りを出力してください。
入力
$H\ \ W\ \ M$
- $1\le H,W,M \le 2 \times 10^5$
- 入力は全て整数である。
出力
条件を満たす行列 $C$ の数を $998244353$ で割った余りを出力してください。
サンプル
サンプル1
入力
2 2 2
出力
10
$C= \begin{pmatrix} 1 & 1 \\ 1 & 1 \\ \end{pmatrix}, \begin{pmatrix} 2 & 2 \\ 2 & 2 \\ \end{pmatrix}, \begin{pmatrix} 2 & 1 \\ 2 & 1 \\ \end{pmatrix}, \begin{pmatrix} 2 & 2 \\ 2 & 1 \\ \end{pmatrix}$ などの $10$ 通りです。
例えば $C=\begin{pmatrix} 2 & 2 \\ 2 & 1 \\ \end{pmatrix}$ は、$a=(2,1),b=(2,1)$ のもとで二つ目の条件を満たします。
サンプル2
入力
1 3 5
出力
125
サンプル3
入力
200000 200000 200000
出力
457157836
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。