Colorful Blocks

题目描述

有 $N$ 个方块排成一行。我们将为这些方块着色。 当且仅当在两种着色方式中存在某个方块被涂成不同颜色时，我们认为这两种着色方式不同。 求满足下列条件的着色方式的数量：

对于每个方块，从 $M$ 种颜色（颜色 $1$ 到颜色 $M$）中选一种来涂色。不要求必须使用所有颜色。 最多允许有 $K$ 对相邻方块被涂成相同颜色。

由于答案可能非常大，请对 $998244353$ 取模输出结果。

输入格式

输入从标准输入给出，格式如下： $N$ $M$ $K$

输出格式

输出答案。

3 2 1

6

100 100 0

73074801

60522 114575 7559

479519525

提示

输入中的所有数值都是整数。 $1 \leq N, M \leq 2 \times 10^5$ $0 \leq K \leq N - 1$下述着色方式满足条件：$112$, $121$, $122$, $211$, $212$, 和 $221$。这里，数字表示方块的颜色。

标签: AtCoder|abc167E

来源

AtCoder|abc167E