Distinct Adjacent

题目描述

有 $N$ 个人，编号从 $1$ 到 $N$，站成一个圆圈。人 $1$ 在人 $2$ 的右边，人 $2$ 在人 $3$ 的右边，…，人 $N$ 在人 $1$ 的右边。 我们将给这 $N$ 个人中的每个人赋一个介于 $0$ 到 $M-1$（包括端点）的整数。
在 $M^N$ 种分配方式中，求满足没有两个相邻的人具有相同整数的分配方式的数量，对 $998244353$ 取模。

输入格式

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

输出格式

输出答案。

3 3

6

4 2

2

987654 456789

778634319

提示

$2 \leq N,M \leq 10^6$ $N$ 和 $M$ 为整数。共有六种符合条件的方式，其中分配给人 $1,2,3$ 的整数分别是 $(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0)$。
共有两种符合条件的方式，其中分配给人 $1,2,3,4$ 的整数分别是 $(0,1,0,1),(1,0,1,0)$。
请务必对 $998244353$ 取模。

标签: AtCoder|abc307E

来源

AtCoder|abc307E