103074: [Atcoder]ABC307 E - Distinct Adjacent
Description
Score : $475$ points
Problem Statement
There are $N$ people numbered from $1$ to $N$ standing in a circle. Person $1$ is to the right of person $2$, person $2$ is to the right of person $3$, ..., and person $N$ is to the right of person $1$.
We will give each of the $N$ people an integer between $0$ and $M-1$, inclusive.
Among the $M^N$ ways to distribute integers, find the number, modulo $998244353$, of such ways that no two adjacent people have the same integer.
Constraints
- $2 \leq N,M \leq 10^6$
- $N$ and $M$ are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$
Output
Print the answer.
Sample Input 1
3 3
Sample Output 1
6
There are six desired ways, where the integers given to persons $1,2,3$ are $(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0)$.
Sample Input 2
4 2
Sample Output 2
2
There are two desired ways, where the integers given to persons $1,2,3,4$ are $(0,1,0,1),(1,0,1,0)$.
Sample Input 3
987654 456789
Sample Output 3
778634319
Be sure to find the number modulo $998244353$.
Input
题意翻译
给定一个长度为 $n$ 的环，每个位置可以填 $1\sim m$，求有多少种方案，满足相邻位置颜色不相同。 translated by @[liangbowen](https://www.luogu.com.cn/user/367488).Output
得分：475分
问题描述
有N个人，编号从1到N，围成一个圆。第1个人在第2个人的右边，第2个人在第3个人的右边，……，第N个人在第1个人的右边。
我们将给这N个人每人分配一个0到M-1之间的整数，包括0和M-1。
在M^N种分配整数的方法中，找出一种方式，使得没有两个相邻的人拥有相同的整数，这种分配方式的数量对998244353取模的结果。
约束条件
- 2≤N,M≤10^6
- N和M都是整数。
输入
输入通过标准输入给出，格式如下：
$N$ $M$
输出
打印答案。
样例输入1
3 3
样例输出1
6
有六种期望的分配方式，其中第1、2、3个人分配的整数分别为(0,1,2)、(0,2,1)、(1,0,2)、(1,2,0)、(2,0,1)、(2,1,0)。
样例输入2
4 2
样例输出2
2
有两种期望的分配方式，其中第1、2、3、4个人分配的整数分别为(0,1,0,1)、(1,0,1,0)。
样例输入3
987654 456789
样例输出3
778634319
请确保找到的结果对998244353取模。