Wrong Answer on test 233 (Hard Version)
Contest: Technocup 2020 - Elimination Round 3
Difficulty rating: 2400
Tags: combinatorics, math

This is the harder version of the problem. In this version, $$$1 \le n \le 2\cdot10^5$$$. You can hack this problem if you locked it. But you can hack the previous problem only if you locked both problems.

The problem is to finish $$$n$$$ one-choice-questions. Each of the questions contains $$$k$$$ options, and only one of them is correct. The answer to the $$$i$$$-th question is $$$h_{i}$$$, and if your answer of the question $$$i$$$ is $$$h_{i}$$$, you earn $$$1$$$ point, otherwise, you earn $$$0$$$ points for this question. The values $$$h_1, h_2, \dots, h_n$$$ are known to you in this problem.

However, you have a mistake in your program. It moves the answer clockwise! Consider all the $$$n$$$ answers are written in a circle. Due to the mistake in your program, they are shifted by one cyclically.

Formally, the mistake moves the answer for the question $$$i$$$ to the question $$$i \bmod n + 1$$$. So it moves the answer for the question $$$1$$$ to question $$$2$$$, the answer for the question $$$2$$$ to the question $$$3$$$, ..., the answer for the question $$$n$$$ to the question $$$1$$$.

We call all the $$$n$$$ answers together an answer suit. There are $$$k^n$$$ possible answer suits in total.

You're wondering, how many answer suits satisfy the following condition: after moving clockwise by $$$1$$$, the total number of points of the new answer suit is strictly larger than the number of points of the old one. You need to find the answer modulo $$$998\,244\,353$$$.

For example, if $$$n = 5$$$, and your answer suit is $$$a=[1,2,3,4,5]$$$, it will submitted as $$$a'=[5,1,2,3,4]$$$ because of a mistake. If the correct answer suit is $$$h=[5,2,2,3,4]$$$, the answer suit $$$a$$$ earns $$$1$$$ point and the answer suite $$$a'$$$ earns $$$4$$$ points. Since $$$4 > 1$$$, the answer suit $$$a=[1,2,3,4,5]$$$ should be counted.

Input format:
The first line contains two integers $$$n$$$, $$$k$$$ ($$$1 \le n \le 2\cdot10^5$$$, $$$1 \le k \le 10^9$$$) — the number of questions and the number of possible answers to each question.

The following line contains $$$n$$$ integers $$$h_1, h_2, \dots, h_n$$$, ($$$1 \le h_{i} \le k)$$$ — answers to the questions.

Output format:
Output one integer: the number of answers suits satisfying the given condition, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first example, valid answer suits are $$$[2,1,1], [2,1,2], [2,1,3], [3,1,1], [3,1,2], [3,1,3], [3,2,1], [3,2,2], [3,2,3]$$$.

Example input:
3 3
1 3 1

Example output:
9

Example input:
5 5
1 1 4 2 2

Example output:
1000

Editorial:
First of all, special judge for $$$k = 1$$$, where the answer is zero.
Let $$$d$$$ be the difference between the points for latest answer suit and the previous one. An valid answer suit means $$$d > 0$$$.
For positions satisfying $$$h_{i} = h_{i \space \mod \space n + 1}$$$, the answer for this position will not affect $$$d$$$. Assume there's $$$t$$$ positions which $$$h_{i} \neq h_{i \space \mod \space n + 1}$$$.
For a fixed position $$$i$$$ which $$$h_{i} \neq h_{i \space \mod \space n + 1}$$$, let your answer for this position is $$$a_{i}$$$ . If $$$a_{i} = h_{i}$$$, then the $$$d$$$ value will decrease by 1. We call this kind of position as a decreasing position. If $$$a_{i} = h_{i \space \mod \space n + 1}$$$, then the $$$d$$$ value increase by 1. We call this kind of position as a increasing position. Otherwise $$$d$$$ value will not be affected, we call this kind of position zero position.
Obviously the number of increasing position should be exact larger then the decreasing position. So let's enumerate the number of zero positions. We can find the answer is equal to $$$k^{n-t} \times \sum_{0 \leq i \leq t - 1}{[(k-2)^i \times \binom{t}{i} \times \sum_{[\frac{t-i}{2}]+1 \leq j \leq t - i}{\binom{t-i}{j}}]}$$$. $$$i$$$ represent the number of zero positions and $$$j$$$ represent the number of increasing positions.
The only problem is how to calculate $$$\sum_{[\frac{t-i}{2}]+1 \leq j \leq t - i}{\binom{t-i}{j}}$$$ quickly. Due to $$$\binom{n}{x} = \binom{n}{n-x}$$$, we can tell that when $$$t - i$$$ is odd, $$$\sum_{[\frac{t-i}{2}]+1 \leq j \leq t - i}{\binom{t-i}{j}} = 2^{t-i-1}$$$. Otherwise it is equal to $$$\frac{2^{t-i} - \binom{t-i}{\frac{t-i}{2}}}{2}$$$.