At Most 2 Colors

题目描述

有一个 $1 \times N$ 的格子，从左到右编号为 $1,2,\dots,N$。 Takahashi 准备了 $C$ 种颜色的颜料，并将每个格子涂成这 $C$ 种颜色中的一种。
并且，在任意连续的 $K$ 个格子中，最多出现两种颜色。
形式上，对任意满足 $1 \le i \le N-K+1$ 的整数 $i$，格子 $i,i+1,\dots,i+K-1$ 中最多出现两种颜色。 Takahashi 有多少种涂色方法？
由于这个数可能很大，请输出对 $998244353$ 取模的结果。

输入格式

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

输出格式

输出答案的整数形式。

3 3 3

21

10 5 2

1024

998 244 353

952364159

提示

输入中的所有数值均为整数。 $2 \le K \le N \le 10^6$ $1 \le C \le 10^9$在这个样例中，我们有一个 $1 \times 3$ 的格子。
在 $27$ 种涂色方法中，有 $6$ 种方法使得所有格子颜色都不同，其余 $21$ 种方法满足任意连续的三个格子中最多有两种颜色。
由于 $C=2$，不管如何涂色，任意连续 $K$ 个格子中最多有两种颜色。
输出对 $998244353$ 取模的结果。

标签: AtCoder|abc279G

来源

AtCoder|abc279G