Wrong Answer on test 233 (Easy Version) (Codeforces 1261D1)
Tags: DP, combinatorics

Your program fails again. This time it gets "Wrong answer on test 233".This is the easier version of the problem. In this version $$$1 \le n \le 2000$$$. You can hack this problem only if you solve and lock both problems.The problem is about a test containing $$$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 2000$$$, $$$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

Sample Outputs:
9

1000

Solution (Python):
import math
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def Extended_Euclid(n, m):
    stack = []
    while m:
        stack.append((n, m))
        (n, m) = (m, n % m)
    if n >= 0:
        (x, y) = (1, 0)
    else:
        (x, y) = (-1, 0)
    for i in range(len(stack) - 1, -1, -1):
        (n, m) = stack[i]
        (x, y) = (y, x - n // m * y)
    return (x, y)

class MOD:

    def __init__(self, p, e=1):
        self.p = p
        self.e = e
        self.mod = self.p ** self.e

    def Pow(self, a, n):
        a %= self.mod
        if n >= 0:
            return pow(a, n, self.mod)
        else:
            assert math.gcd(a, self.mod) == 1
            x = Extended_Euclid(a, self.mod)[0]
            return pow(x, -n, self.mod)

    def Build_Fact(self, N):
        assert N >= 0
        self.factorial = [1]
        self.cnt = [0] * (N + 1)
        for i in range(1, N + 1):
            ii = i
            self.cnt[i] = self.cnt[i - 1]
            while ii % self.p == 0:
                ii //= self.p
                self.cnt[i] += 1
            self.factorial.append(self.factorial[-1] * ii % self.mod)
        self.factorial_inve = [None] * (N + 1)
        self.factorial_inve[-1] = self.Pow(self.factorial[-1], -1)
        for i in range(N - 1, -1, -1):
            ii = i + 1
            while ii % self.p == 0:
                ii //= self.p
            self.factorial_inve[i] = self.factorial_inve[i + 1] * ii % self.mod

    def Fact(self, N):
        return self.factorial[N] * pow(self.p, self.cnt[N], self.mod) % self.mod

    def Fact_Inve(self, N):
        if self.cnt[N]:
            return None
        return self.factorial_inve[N]

    def Comb(self, N, K, divisible_count=False):
        if K < 0 or K > N:
            return 0
        retu = self.factorial[N] * self.factorial_inve[K] * self.factorial_inve[N - K] % self.mod
        cnt = self.cnt[N] - self.cnt[N - K] - self.cnt[K]
        if divisible_count:
            return (retu, cnt)
        else:
            retu *= pow(self.p, cnt, self.mod)
            retu %= self.mod
            return retu

def NTT_Pow(polynomial, N):
    prim_root = 3
    prim_root_inve = MOD(mod).Pow(prim_root, -1)

    def DFT(polynomial, inverse=False):
        dft = polynomial + [0] * ((1 << n) - len(polynomial))
        if inverse:
            for bit in range(1, n + 1):
                a = 1 << bit - 1
                x = pow(prim_root, mod - 1 >> bit, mod)
                U = [1]
                for _ in range(a):
                    U.append(U[-1] * x % mod)
                for i in range(1 << n - bit):
                    for j in range(a):
                        s = i * 2 * a + j
                        t = s + a
                        (dft[s], dft[t]) = ((dft[s] + dft[t] * U[j]) % mod, (dft[s] - dft[t] * U[j]) % mod)
            x = pow((mod + 1) // 2, n)
            for i in range(1 << n):
                dft[i] *= x
                dft[i] %= mod
        else:
            for bit in range(n, 0, -1):
                a = 1 << bit - 1
                x = pow(prim_root_inve, mod - 1 >> bit, mod)
                U = [1]
                for _ in range(a):
                    U.append(U[-1] * x % mod)
                for i in range(1 << n - bit):
                    for j in range(a):
                        s = i * 2 * a + j
                        t = s + a
                        (dft[s], dft[t]) = ((dft[s] + dft[t]) % mod, U[j] * (dft[s] - dft[t]) % mod)
        return dft
    n = ((len(polynomial) - 1) * N).bit_length()
    ntt = DFT(polynomial)
    for i in range(1 << n):
        ntt[i] = pow(ntt[i], N, mod)
    ntt = DFT(ntt, inverse=True)
    return ntt
(N, K) = map(int, readline().split())
A = list(map(int, readline().split()))
if K == 1:
    ans = 0
else:
    mod = 998244353
    cnt = 0
    for i in range(N):
        if A[i] != A[(i + 1) % N]:
            cnt += 1
    dp = NTT_Pow([1, K - 2, 1], cnt)
    for i in range(len(dp)):
        dp[i] *= pow(K, N - cnt, mod)
        dp[i] %= mod
    ans = sum(dp[cnt + 1:2 * cnt + 1]) % mod
print(ans)

Solution (Python):
(n, k) = [int(kk) for kk in input().strip().split(' ')]
h = [int(kk) for kk in input().strip().split(' ')]
fact = [1] * (n + 1)
mod = 998244353
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i % mod

def inv(x):
    return pow(x, mod - 2, mod)

def C(n, k):
    return fact[n] * inv(fact[k]) * inv(fact[n - k]) % mod
ng = 0
for i in range(n):
    if h[i] == h[i - 1]:
        ng += 1
np = n - ng
totposs = pow(k, np)
possegales = [C(np, kk) * C(np - kk, kk) * pow(k - 2, np - 2 * kk, mod) for kk in range(np // 2 + 1)]
res = (totposs - sum(possegales) % mod + mod) % mod * inv(2) * pow(k, ng, mod)
res %= mod
print(res)

Solution (Python):
(n, k) = [int(kk) for kk in input().strip().split(' ')]
h = [int(kk) for kk in input().strip().split(' ')]
fact = [1] * (n + 1)
mod = 998244353
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i % mod

def inv(x):
    return pow(x, mod - 2, mod)

def C(n, k):
    return fact[n] * inv(fact[k]) * inv(fact[n - k]) % mod
ng = 0
for i in range(n):
    if h[i] == h[i - 1]:
        ng += 1
np = n - ng
totposs = pow(k, np)
possegales = [C(np, kk) * C(np - kk, kk) * pow(k - 2, np - 2 * kk) for kk in range(np // 2 + 1)]
res = (totposs - sum(possegales) % mod + mod) % mod * inv(2) * pow(k, ng, mod)
res %= mod
print(res)