CF1227F2 Wrong Answer on test 233 (Hard Version)

你的程序又出错了。这一次它在第 $233$ 个测试点上得到了“答案错误”。 这是该问题的更难版本。在本版本中，$1 \le n \le 2\cdot10^5$。如果你锁定了本题，可以对其进行 hack。但只有在你同时锁定了两个问题时，才能 hack 前一个问题。 问题描述如下：你需要完成 $n$ 道单选题。每道题有 $k$ 个选项，且只有一个选项是正确的。第 $i$ 道题的正确答案是 $h_i$，如果你对第 $i$ 道题的作答为 $h_i$，则你获得 $1$ 分，否则该题得 $0$ 分。所有 $h_1, h_2, \dots, h_n$ 在本题中均已知。 然而，你的程序有一个错误。它会将答案顺时针移动一位！假设所有 $n$ 个答案排成一个环。由于程序的错误，它们会循环右移一位。 具体来说，程序会将第 $i$ 道题的答案移动到第 $(i \bmod n) + 1$ 道题的位置。也就是说，第 $1$ 题的答案被移动到第 $2$ 题，第 $2$ 题的答案被移动到第 $3$ 题，……，第 $n$ 题的答案被移动到第 $1$ 题。 我们把所有 $n$ 个答案合起来称为一个“答案序列”。一共有 $k^n$ 种可能的答案序列。 你想知道，有多少个答案序列满足如下条件：经过顺时针移动 $1$ 位后，新答案序列的总得分严格大于原序列的得分。你需要输出满足条件的答案序列数，结果对 $998\,244\,353$ 取模。 例如，若 $n=5$，你的答案序列为 $a=[1,2,3,4,5]$，由于程序错误，提交的答案为 $a'=[5,1,2,3,4]$。若正确答案序列为 $h=[5,2,2,3,4]$，则 $a$ 得 $1$ 分，$a'$ 得 $4$ 分。由于 $4>1$，所以 $a=[1,2,3,4,5]$ 应被计入答案。

第一行包含两个整数 $n$、$k$（$1 \le n \le 2\cdot10^5$，$1 \le k \le 10^9$）——题目数量和每题的选项数。 第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le k$）——每道题的正确答案。

输出一个整数，表示满足条件的答案序列数，对 $998\,244\,353$ 取模。

对于第一个样例，合法的答案序列有 $[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]$。 由 ChatGPT 4.1 翻译