Wrong Answer on test 233 (Hard Version) (Codeforces 1227F2)
Tags: Math, combinatorics

Your program fails again. This time it gets "Wrong answer on test 233".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: 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: Output one integer: the number of answers suits satisfying the given condition, modulo $$$998\,244\,353$$$.

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]$$$.

Sample Inputs:
3 3
1 3 1

5 5
1 1 4 2 2

6 2
1 1 2 2 1 1

Sample Outputs:
9

1000

16

Solution (Python):
def main():
    M = 998244353
    (n, k, *h) = map(int, open(0).read().split())
    m = sum((i != j for (i, j) in zip(h, h[1:] + h[:1])))
    f = [0] * (m + 1)
    f[0] = b = 1
    for i in range(1, m + 1):
        f[i] = b = b * i % M
    inv = [0] * (m + 1)
    inv[m] = b = pow(f[m], M - 2, M)
    for i in range(m, 0, -1):
        inv[i - 1] = b = b * i % M
    comb = lambda n, k: f[n] * inv[n - k] * inv[k] % M
    print((pow(k, m, M) - sum((comb(m, i) * comb(m - i, i) * pow(k - 2, m - i - i, M) for i in range(m // 2 + 1)))) * pow(k, n - m, M) * pow(2, M - 2, M) % M)
main()

Solution (Python):
from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
    return map(int, sys.stdin.readline().rstrip().split())

def RLL():
    return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
    return int(input())
farr = [1]
ifa = []

def fact(x, mod=0):
    if mod:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr) % mod)
    else:
        while x >= len(farr):
            farr.append(farr[-1] * len(farr))
    return farr[x]

def ifact(x, mod):
    global ifa
    ifa.append(pow(farr[-1], mod - 2, mod))
    for i in range(x, 0, -1):
        ifa.append(ifa[-1] * i % mod)
    ifa = ifa[::-1]

def per(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return fact(i) // fact(i - j)
    return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
    if i < j:
        return 0
    if not mod:
        return per(i, j) // fact(j)
    return per(i, j, mod) * ifa[j] % mod

def catalan(n):
    return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
    while l < r:
        mid = (l + r) // 2
        if t > f(mid):
            l = mid + 1
        else:
            r = mid
    return l

def rinc(f, t, l, r):
    while l < r:
        mid = (l + r + 1) // 2
        if t < f(mid):
            r = mid - 1
        else:
            l = mid
    return l

def ldec(f, t, l, r):
    while l < r:
        mid = (l + r) // 2
        if t < f(mid):
            l = mid + 1
        else:
            r = mid
    return l

def rdec(f, t, l, r):
    while l < r:
        mid = (l + r + 1) // 2
        if t > f(mid):
            r = mid - 1
        else:
            l = mid
    return l

def isprime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def binfun(x):
    c = 0
    for w in arr:
        c += ceil(w / x)
    return c

def lowbit(n):
    return n & -n

def inverse(a, m):
    a %= m
    if a <= 1:
        return a
    return (1 - inverse(m, a) * m) // a % m

class BIT:

    def __init__(self, arr):
        self.arr = arr
        self.n = len(arr) - 1

    def update(self, x, v):
        while x <= self.n:
            self.arr[x] += v
            x += x & -x

    def query(self, x):
        ans = 0
        while x:
            ans += self.arr[x]
            x &= x - 1
        return ans

class smt:

    def __init__(self, l, r, arr):
        self.l = l
        self.r = r
        self.value = (1 << 31) - 1 if l < r else arr[l]
        mid = (l + r) // 2
        if l < r:
            self.left = smt(l, mid, arr)
            self.right = smt(mid + 1, r, arr)
            self.value &= self.left.value & self.right.value

    def setvalue(self, x, val):
        if self.l == self.r:
            self.value = val
            return
        mid = (self.l + self.r) // 2
        if x <= mid:
            self.left.setvalue(x, val)
        else:
            self.right.setvalue(x, val)
        self.value = self.left.value & self.right.value

    def ask(self, l, r):
        if l <= self.l and r >= self.r:
            return self.value
        val = (1 << 31) - 1
        mid = (self.l + self.r) // 2
        if l <= mid:
            val &= self.left.ask(l, r)
        if r > mid:
            val &= self.right.ask(l, r)
        return val

class DSU:

    def __init__(self, n):
        self.c = [-1] * n

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def find(self, x):
        if self.c[x] < 0:
            return x
        self.c[x] = self.find(self.c[x])
        return self.c[x]

    def union(self, u, v):
        (u, v) = (self.find(u), self.find(v))
        if u == v:
            return False
        if self.c[u] < self.c[v]:
            (u, v) = (v, u)
        self.c[u] += self.c[v]
        self.c[v] = u
        return True

    def size(self, x):
        return -self.c[self.find(x)]

class UFS:

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.ranks = [0] * n

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, u, v):
        (pu, pv) = (self.find(u), self.find(v))
        if pu == pv:
            return False
        if self.ranks[pu] >= self.ranks[pv]:
            self.parent[pv] = pu
            if self.ranks[pv] == self.ranks[pu]:
                self.ranks[pu] += 1
        else:
            self.parent[pu] = pv

def Prime(n):
    c = 0
    prime = []
    flag = [0] * (n + 1)
    for i in range(2, n + 1):
        if not flag[i]:
            prime.append(i)
            c += 1
        for j in range(c):
            if i * prime[j] > n:
                break
            flag[i * prime[j]] = prime[j]
            if i % prime[j] == 0:
                break
    return prime

def dij(s, graph):
    d = {}
    d[s] = 0
    heap = [(0, s)]
    seen = set()
    while heap:
        (dis, u) = heappop(heap)
        if u in seen:
            continue
        for v in graph[u]:
            if v not in d or d[v] > d[u] + graph[u][v]:
                d[v] = d[u] + graph[u][v]
                heappush(heap, (d[v], v))
    return d

def GP(it):
    return [(ch, len(list(g))) for (ch, g) in groupby(it)]

class DLN:

    def __init__(self, val):
        self.val = val
        self.pre = None
        self.next = None
t = 1
for i in range(t):
    mod = 998244353
    (n, k) = RL()
    h = RLL()
    res = GP(h)
    c = 0
    for (ch, cnt) in res:
        c += cnt - 1
    n = len(res)
    if res[-1][0] == res[0][0]:
        c += 1
        n -= 1
    ans = pow(k, c, mod)
    tmp = pow(k, n, mod)
    fact(n, mod)
    ifact(n, mod)
    p = [1]
    for i in range(n):
        p.append(p[-1] * (k - 2) % mod)
    for x in range(n // 2 + 1):
        tmp = (tmp - p[n - 2 * x] * fact(n, mod) % mod * ifa[x] % mod * ifa[x] % mod * ifa[n - 2 * x] % mod) % mod
    ans = ans * tmp % mod * pow(2, mod - 2, mod) % mod
    print(ans)

Solution (Python):
M = 998244353

class Factorial:

    def __init__(self, n):
        self.f = f = [0] * (n + 1)
        f[0] = b = 1
        for i in range(1, n + 1):
            f[i] = b = b * i % M
        self.inv = inv = [0] * (n + 1)
        inv[n] = b = pow(self.f[n], M - 2, M)
        for i in range(n, 0, -1):
            inv[i - 1] = b = b * i % M

    def factorial(self, i):
        return self.f[i]

    def ifactorial(self, i):
        return self.inv[i]

    def comb(self, n, k):
        if n >= k:
            return self.f[n] * self.inv[n - k] * self.inv[k] % M
        else:
            return 0

def main():
    (n, k, *h) = map(int, open(0).read().split())
    m = sum((i != j for (i, j) in zip(h, h[1:] + h[:1])))
    comb = Factorial(m).comb
    print((pow(k, m, M) - sum((comb(m, i) * comb(m - i, i) * pow(k - 2, m - i - i, M) for i in range(m // 2 + 1)))) * pow(k, n - m, M) * pow(2, M - 2, M) % M)
main()