No.1836 Max Matrix
タグ : / 解いたユーザー数 92
作問者 :
Sumitacchan
/ テスター :
👑 
hitonanode
ygussany
Problem Statement
How many matrices $C$ with $H$ rows and $W$ columns satisfy all of the following conditions?
- Each entry $C_{i,j}\ (1\le i\le H,1\le j\le W)$ of $C$ is an integer between $1$ and $M$, inclusive.
- There exists a pair of integer sequences $a=(a_1,a_2,\dots,a_H),b=(b_1,b_2,\dots,b_W)$ such that $C_{i,j}=\max(a_i,b_j)$ holds for all integers $i,j\ (1\le i\le H,1\le j\le W)$.
Since the answer can be very large, output it modulo $998244353$.
Input
$H\ \ W\ \ M$
- $1\le H,W,M \le 2 \times 10^5$
- All inputs are integers.
Output
Output the number of matrices $C$ satisfying the conditions, modulo $998244353$.
Sample
Sample 1
Input
2 2 2
Output
10
There are $10$ such matrices, including $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}$.
For example, $C=\begin{pmatrix} 2 & 2 \\ 2 & 1 \\ \end{pmatrix}$ satisfies the second condition with $a=(2,1),b=(2,1)$.
Sample 2
Input
1 3 5
Output
125
Sample 3
Input
200000 200000 200000
Output
457157836
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。