D. 最大值的最小值，最小值的最大值

第 230 场 AtCoder Regular Contest++

最大值的最小值，最小值的最大值

Min Max Matrix

AtCoder

⌀ 2395

原题

← CE →

最大值的最小值，最小值的最大值AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

You are given positive integers $H$ , $W$ , and $M$ .

给定正整数 $H$ 、 $W$ 和 $M$ 。AI (CI翻译)

Find the number, modulo $998244353$ , of $H\times W$ matrices $A$ , each of whose elements is an integer between $1$ and $M$ (inclusive), satisfying the following condition.

求满足以下条件的 $H\times W$ 矩阵 $A$ 的数量，对 $998244353$ 取模。矩阵中的每个元素都是 $1$ 到 $M$ （含）之间的整数。AI (CI翻译)

[ \min_{1\le i\le H}\max_{1\le j\le W}A_{i,j}=\max_{1\le j\le W}\min_{1\le i\le H}A_{i,j} ]

[ \min_{1\le i\le H}\max_{1\le j\le W}A_{i,j}=\max_{1\le j\le W}\min_{1\le i\le H}A_{i,j} ]AI (CI翻译)

Here, $A_{i,j}$ denotes the element at the $i$ -th row and $j$ -th column of matrix $A$ .

这里， $A_{i,j}$ 表示矩阵 $A$ 中第 $i$ 行、第 $j$ 列的元素。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

$1 \le H,W \le 200$
$1 \le M \le 10^8$
All input values are integers.

$1 \le H,W \le 200$
$1 \le M \le 10^8$
输入的所有数值均为整数。

AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入按以下格式给出：AI (CI翻译)

H W M

H W M

AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output the answer.

输出答案。AI (CI翻译)

样例

Input #1

2 2 3

Output #1

For example, $A=\begin{pmatrix} 1 & 2\\ 2 & 3\end{pmatrix}$ satisfies the condition. - $\displaystyle\min_{1\le i\le H}\max_{1\le j\le W}A_{i,j}=\max_{1\le j\le W}\min_{1\le i\le H}A_{i,j}=2$ holds. On the other hand, $A=\begin{pmatrix} 1 & 3\\ 3 & 2\end{pmatrix}$ does not satisfy the condition. - $\displaystyle\min_{1\le i\le H}\max_{1\le j\le W}A_{i,j}=3,\max_{1\le j\le W}\min_{1\le i\le H}A_{i,j}=2$. There are $67$ matrices $A$ satisfying the condition.

Input #2

99 82 44353

Output #2

213254234

题目信息

题号

arc230_d

所属比赛

第 230 场 AtCoder Regular Contest++

时间限制

4 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。