← 返回题目列表

Codeforces · 1227/F2

F2. 测试 233 的错误答案(困难版)

中文机器翻译题面 查看原题

这是问题的更难版本。在此版本中,$$$1 \le n \le 2\cdot10^5$$$。如果你锁定了这个问题,你就可以解决这个问题。但只有当你锁定了这两个问题时,你才能破解前一个问题。

问题是完成$$$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$$$为模。

示例

输入 #1

3 3
1 3 1

输出 #1

9

输入 #2

5 5
1 1 4 2 2

输出 #2

1000

输入 #3

6 2
1 1 2 2 1 1

输出 #3

16

注意

对于第一个示例,有效答案花色为 $$$[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]$$$。