Problem:


Score : 500 points

Problem Statement

There are N blocks arranged in a row. Let us paint these blocks.

We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.

Find the number of ways to paint the blocks under the following conditions:

For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.

There may be at most K pairs of adjacent blocks that are painted in the same color.

Since the count may be enormous, print it modulo 998244353.

Constraints

All values in input are integers.

1 \leq N, M \leq 2 \times 10^5

0 \leq K \leq N - 1

Input

Input is given from Standard Input in the following format:

N M K

Output

Print the answer.

Sample Input 1

3 2 1

Sample Output 1

6

The following ways to paint the blocks satisfy the conditions: 112, 121, 122, 211, 212, and 221. Here, digits represent the colors of the blocks.

Sample Input 2

100 100 0

Sample Output 2

73074801

Sample Input 3

60522 114575 7559

Sample Output 3

479519525



Sample input:
3 2 1


Sample output:
6

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Combination:
    def __init__(self, n, mod):

        g1 = [1, 1]
        g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, n + 1):
            g1.append((g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod//i)) % mod)
            g2.append((g2[-1] * inverse[-1]) % mod)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.MOD



@mt
def slv(N, M, K):
    m = Mod(998244353)
    C = Combination(N, 998244353)

    ans = 0
    col = M
    for x in range(N-1, -1, -1):
        tmp = col
        tmp = m.mul(tmp, C(N-1, x))
        if x <= K:
            ans = m.add(ans, tmp)
        col = m.mul(col, M-1)
    return ans


def main():
    N, M, K = read_int_n()
    print(slv(N, M, K))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())

mod = 998244353

ans = 0

facts = [1 for i in range(N+1)]
invs = [1 for i in range(N+1)]

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

for i in range(1, N+1):
    facts[i] = facts[i-1] * i % mod
    invs[i] = inv(facts[i])

def comb(n, r):
    return facts[n] * invs[r] * invs[n-r] % mod

for i in range(K+1):
    d = M * pow(M-1, N-i-1, mod) * comb(N-1, i)
    ans = (ans + d % mod) % mod

print(ans)

Submission status: Accepted

Solution code:
def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))
n,m,k = mp()
mod = 998244353
conb = [1]
pows = [pow(m-1, n-1-k, mod)]
for i in range(1,k+1):
    conb.append(conb[i-1]*(n-i)*pow(i,mod-2,mod) % mod)
    pows.append(pows[i-1]*(m-1) % mod)
pows.reverse()
# print(conb, pows)
ans = 0
for i in range(k+1):
    ans += m * conb[i] * pows[i]
    ans %= mod
print(ans)

# print(conb)
# print(pows)
# exit()
# now_comb = 1
# now_pow = pow(m-1, n-1, mod)
# ans = now_pow*m
# for i in range(1, k+1):
#     u1 = (now_comb * (n-i) * pow(i, mod-2, mod)) % mod
#     u2 = (now_pow * pow(m-1, mod-2, mod)) % mod
#     now_comb = u1
#     now_pow = u2
#     ans += u1*u2*m
#     ans %= mod
# print(ans%mod)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from math import factorial

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N, M, K = map(int, input().split())
    MOD = 998244353
    fac = [0] * (N + 10)
    finv = [0] * (N + 10)
    inv = [0] * (N + 10)
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, N + 2):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    def COM(n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

    ans = 0
    for k in range(K + 1):
        ans += COM(N - 1, k) * ((M % MOD) * pow(M - 1, (N - k - 1), MOD)) % MOD

    print(ans % MOD)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M,K = map(int,input().split())
ans = 0
mod = 998244353

def modinv(a, mod=998244353):
    return pow(a, mod-2, mod)

fac = [0]*(N+1)
fac[0] = 1
fac[1] = 1
for i in range(2,N+1):
    fac[i] = fac[i-1] * i % mod

def combi(n,r,mod=998244353):
    return( ( fac[n] * modinv(fac[r]) )%mod * modinv(fac[n-r]) % mod)

z = M*(pow(M-1,N-K-1,mod))%mod
for k in range(K,-1,-1):
    c = z*combi(N-1,k)%mod
    ans += c
    z = z*(M-1)%mod

print(ans%mod)

Submission status: Accepted

Solution code:
#coding: utf-8
N, M, K = map(int, input().split())
mod = 998244353

def cmb(n, k, mod, fac, ifac):    
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod

def make_tables(mod, n):
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)
 
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

f = [0 for _ in range(N)]
for i in range(N):
    if i == 0:
        f[i] = M
    else:
        f[i] = (f[i-1] * (M-1)) % mod
if K == 0:
    print(f[N-1])
else:
    fac, ifac = make_tables(mod, N)
    ans = 0
    c = 1
    for i in range(K+1):
        ans += f[N-1-i] * c
        ans %= mod
        c = cmb(N-1, i+1, mod, fac, ifac)
    print(ans % mod)

Submission status: Accepted

Solution code:
import sys
N,M,K= list(map(int, input().split()))
mod = 998244353

if N == 1:
    print(M)
    sys.exit()


def cmbinit(n):
    fac = [0]*n
    finv = [0]*n
    inv = [0]*n
    fac[0]=fac[1] = 1
    finv[0]=finv[1] = 1
    inv[1] = 1
    for i in range(2,n):
        fac[i] = fac[i-1]*i %mod
        inv[i] = mod - inv[mod%i] * (mod//i) %mod
        finv[i] = finv[i-1] * inv[i]%mod
    
    return fac,finv

def cmb(n,r,fac,finv):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0

    return fac[n] * (finv[r] * finv[n - r] % mod) %mod




ans = 0
fac,finv = cmbinit(N)
for k in range(K+1):
    ans += (M * pow(M-1, N-k-1, mod) * cmb(N-1,k,fac,finv))%mod


print(ans%mod)

Submission status: Accepted

Solution code:
def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fac[n] * finv[r] * finv[n-r] % p

N , M , K = map(int,input().split())
MOD = 998244353

fac = [-1]*(N+1); fac[0] = 1; fac[1] = 1
finv = [-1]*(N+1); finv[0] = 1; finv[1] = 1
inv = [-1]*(N+1); inv[0] = 0; inv[1] = 1
for i in range(2,N+1):
  fac[i] = fac[i-1]*i%MOD
  inv[i] = MOD - inv[MOD%i]*(MOD//i)%MOD
  finv[i] = finv[i-1]*inv[i]%MOD

ans = 0
for t in range(K+1):
    temp = M*pow(M-1,N-t-1,MOD)
    temp = temp*cmb(N-1,t,MOD)
    ans = (ans+temp)%MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

class ModTools:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        inverse = [1] * MAX
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, -1, -1):
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 """

        if n < r: return 0
        r = min(r, n-r)
        numerator = self.fact[n]
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

N, M, K = MAP()

mt = ModTools(N, MOD)
ans = 0
for k in range(K+1):
    ans += M * pow(M-1, N-k-1, MOD) * mt.nCr(N-1, k)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
mod=998244353
if m==1:print(0 if k!=n-1 else 1);exit()
fact=[1]*(n-1+1)
inv=[1]*(n-1+1)
for i in range(2,n-1+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n-1,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return fact[x]*inv[y]%mod*inv[x-y]%mod
ans=0
po=pow(m-1,n-1,mod)*m%mod
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)%mod
for i in range(k+1):
    ans+=comb(n-1,i)*po%mod
    po*=iii
    po%=mod
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

fac = [1, 1]     # 元テーブル
f_inv = [1, 1]   # 逆元テーブル
inv = [0, 1]     # 逆元テーブル計算用テーブル

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)

def cmb(n, r, mod):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def main():
    N,M,K = map(int, readline().split())

    MOD = 998244353
    prepare(N + 10, MOD)

    if M == 1 and K == N - 1:
        print(1)
        exit()

    m = M
    for _ in range(N-1):
        m *= M - 1
        m %= MOD

    ans = 0
    for k in range(K+1):
        ans += (m * cmb(N-1, k, MOD)) % MOD
        ans %= MOD

        m *= pow(M-1, MOD-2, MOD)
        m %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 998244353
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m, k = mi()

    FACT = [1] * (n + 1)
    for i in range(1, n + 1):
        FACT[i] = (i * FACT[i - 1]) % mod

    def comb(n, r, m):
        numerator = FACT[n]
        denominator = pow(FACT[n - r] * FACT[r], m - 2, m)
        return (numerator * denominator) % m
    
    ans = 0
    for j in range(k + 1):
        ans = (ans + (m * pow(m - 1, n - j - 1, mod) * comb(n - 1, j, mod)) % mod) % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy
n,m,k = map(int, input().split())
if m==1:
    if (n-1==k):
        print(1)
    else:
        print(0)
    exit()

mod = 998244353
if (n-1==k):
    print(pow(m,n,mod))
    exit()
#dp[i][j]:i個まで、j組
def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.deepcopy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.deepcopy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

ans = m*pow(m-1,n-1,mod)
ans %= mod
#print(ans)
p = pow(m-1,n-k-2,mod)
#com(n-1,i,mod)
c = com(n-1,k+1,mod)
#print(c)
for i in range(k,0,-1):
    p *= (m-1)
    p %= mod
    c *= (i+1)
    c *= pow(n-i-1,mod-2,mod)
    c %= mod
    ans += m * p * c
    ans %= mod
    #print(m-1,i,mod)
    #print(ans)
print(ans)

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
mod=998244353

#階乗と階乗逆元
fact=[0]*220000
invfact=[0]*220000
fact[0]=1
for i in range(1,220000):
    fact[i]=fact[i-1]*i%mod
invfact[220000-1]=pow(fact[220000-1],mod-2,mod)
for i in range(220000-2,-1,-1):
    invfact[i]=invfact[i+1]*(i+1)%mod

#↑を用いたnCk
def nCk(n,k):
    if k<0 or n<k:return 0
    return fact[n]*invfact[k]*invfact[n-k]%mod

ans=0
for i in range(K+1):
    ans+=M*pow(M-1,N-i-1,mod)*nCk(N-1,i)%mod

print(ans%mod)

Submission status: Accepted

Solution code:
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def nCr(self, n, r):
        r = min(n - r, r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def nHr(self, n, r):
        return self.nCr(n - 1 + r, r)


def main():
    from itertools import accumulate
    MOD = 998244353

    N, M, K = map(int, input().split())

    cc = Calc(max_value=N, mod=MOD)
    *m_1, = accumulate([1] + [M - 1] * (N - 1), func=lambda a, b: a * b % MOD)

    ans = 0
    for bond in range(K + 1):
        t = cc.nCr(N - 1, bond)  # 結合位置の候補を左側のブロック総数N-1個からbond個選ぶ
        t = t * m_1[N - 1 - bond] % MOD  # N-bond個の相異なる色で塗り分けたときの2個目以降の色の塗り方
        ans = (ans + t) % MOD
    ans = ans * M % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p

N, M, K = map(int, input().split())

p = 998244353
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ans = 0
col = M
for x in range(N - 1, -1, -1):
    now = col
    now *= cmb(N - 1, x, p)
    now %= p
    if x <= K:
        ans += now
        ans %= p
    col *= (M - 1)
    col %= p
print(ans)

Submission status: Accepted

Solution code:
def cmb(n, k, mod, fac, ifac):    
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

n,m,k = map(int,input().split())
f=[0 for _ in range(n)]
mod=998244353
for i in range(n):
    if i == 0:
        f[i]=m
    else:
        f[i]=(f[i-1]*(m-1))%mod
c=1
ans=0
if k==0:
    print(f[n-1])
    exit()
fac, ifac = make_tables(mod, n)
for i in range(k+1):
    ans+=f[n-1-i]*c
    ans%=mod
    #print(f[n-1-i],c)
    
    c=cmb(n-1,i+1,mod,fac,ifac)

print(ans%mod)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
MOD = 998244353

def modpow(a, n, p):
  if n == 0:
    return 1
  if n == 1:
    return a % p 
  elif n % 2 == 1:
    return a * modpow(a, n-1, p) % p
  else:
    return modpow(a, n//2, p) **2 % p
dp = [0]*(k+1)
dp[0] = m* modpow(m-1, n-1, MOD) % MOD
bunsi = 1
bunbo = 1
for j in range(1, k+1):
  bunsi = bunsi * (n-j) % MOD
  bunbo = bunbo * j % MOD

  comb = bunsi * modpow(bunbo, MOD-2, MOD) % MOD
  dp[j] = (m * modpow(m-1, n-1-j, MOD)*comb % MOD + dp[j-1]) % MOD
print(dp[k])

Submission status: Accepted

Solution code:
from functools import reduce
mod = 998244353

N, M, K = map(int, input().split())
C = 1
ans = (M*pow(M-1, (N-1), mod))%mod
k = 1
while k <= K and k < N:
  C *= (N-k)*pow(k, mod-2, mod)
  C %= mod
  a = (C*M*pow(M-1, (N-k-1), mod))%mod
  ans = (ans+a)%mod
  k += 1
print(ans)

Submission status: Accepted

Solution code:
def ext_euler(a, b):
    if b == 0:
        return 1, 0, a
    else:
        y, x, v = ext_euler(b, a%b)
        y -= (a//b) * x
        return x, y, v


def mod_inv(x, mod):
    if x > mod:
        ans, _, _ = ext_euler(x, mod)
    else:
        _, ans, _ = ext_euler(mod, x)
    return ans % mod


def comb_list(n, mod):
    ret = [1 for _ in range(n + 1)]
    for k in range(n):
        c = ret[k]
        c *= (n - k)
        c %= mod
        c *= mod_inv(k + 1, mod)
        c %= mod
        ret[k + 1] = c
    return ret


def main():
    MOD = 998244353
    N, M, K = list(map(int, input().split(' ')))
    # x pair of same color
    # -> M * (M - 1)**(N - 1 - x) * (N - 1)_C_x
    # -> sum up from x = min(K, N - 1) to x = 0
    patterns = [0 for _ in range(N)]
    comb = comb_list(N - 1, MOD)
    pw = M
    for x in range(N - 1, -1, -1):
        patterns[x] = pw * comb[x]
        patterns[x] %= MOD
        pw *= (M - 1)
        pw %= MOD
    ans = 0
    for x in range(min(K, N - 1) + 1):
        ans += patterns[x]
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

N, M, K = map(int, input().split())
mod = 998244353

table = [0]
inv_table = [0]
M_table = []

tmp = pow(M - 1, N - 1, mod)
for i in range(K + 1):
    if i > 0:
        tmp *= pow(M - 1, mod - 2, mod)
        tmp %= mod
    M_table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= i
    tmp %= mod
    table.append(tmp)

tmp = 1
for i in range(1, N + 1):
    tmp *= pow(i, mod - 2, mod)
    tmp %= mod
    inv_table.append(tmp)

def cmb(n, r):
    if r == 0:
        return 1
    if n == r:
        return 1
    return table[n] * inv_table[r] * inv_table[n - r]

if M == 1:
    if N - 1 == K:
        print(1)
    else:
        print(0)
    exit()

ans = 0
for i in range(K + 1):
    ans += M * M_table[i] * cmb(N - 1, i)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
N,M,K = list(map(int,input().split()))
MOD = 998244353
 
fac = [1] * (N+1)
inv = [1] * (N+1)
ifac = [1] * (N+1)
for i in range(2,N+1):
    fac[i]=(fac[i-1]*i)%MOD
    inv[i]= -(inv[MOD%i]*(MOD//i))%MOD
    ifac[i]=(ifac[i-1]*inv[i])%MOD
 
cmbarr = [1] * N
for r in range(N-1):
    cmbarr[r+1] = cmbarr[r] * (N - 1 - r) * inv[r + 1] % MOD
 
A = [M*pow(M-1,N-1-i,MOD)*cmbarr[i] % MOD for i in range(K+1)]
print(sum(A) % MOD)

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline

N, M, K = map(int, input().split())
mod = 998244353


C = [-1] * (N + 1)


def comb(n, r):
    if r > n - r:
        C[r] = C[n - r]

    if r == 0:
        C[0] = 1

    if C[r] != -1:
        return C[r]
    else:
        C[r] = comb(n, r - 1) * (n + 1 - r) * pow(r, mod - 2, mod)
        C[r] %= mod
        return C[r]


ans = 0

for i in range(K + 1):
    ans += M * pow(M - 1, N - 1 - i, mod) * comb(N - 1, i)
    ans %= mod

print(ans)
# print(C)

Submission status: Accepted

Solution code:
import time

N, M, K = map(int, input().split())
rlt = 0
# ①nCrの各項のmod(10^9+7)を事前計算
p = 998244353
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
  fact.append((fact[-1] * i) % p)
  inv.append((-inv[p % i] * (p // i)) % p)
  factinv.append((factinv[-1] * inv[-1]) % p)

# ②事前計算した項を掛け合わせ
def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fact[n] * factinv[r] * factinv[n-r] % p

Mp = [0]*N
Mp[-1] = M 
for i in range(1, N):
  Mp[-i-1] = Mp[-i]*(M-1) % p
#print(Mp)
for k in range(K+1):
  #print(cmb(N-1,k,p), Mp[k])
  rlt += cmb(N-1,k,p)*Mp[k]
  rlt %= p

print(rlt)

Submission status: Accepted

Solution code:
MOD = 998244353
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def cmb(fact, n ,r):
    return ModInt(1) * fact[n] / fact[n - r] / fact[r]

def solve(N, M, K):
    fact = [ModInt(1)]
    for i in range(1, N + 1):
        fact.append(fact[i -1] * i)

    ret = ModInt(0)
    for x in range(K + 1):
        ret += cmb(fact, N - 1, x) * M * pow(M - 1, N - x - 1, MOD)
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    print(solve(N, M, K))

Submission status: Accepted

Solution code:
MOD = 998244353
N, M, K = map(int, input().split())
Mp = [0]*(K+1)
nck = [0]*(K+1)
nck[0] = 1
ans = 0
comb = 1
for i in range(K+1):
  t = 1
  t *= M
  t %= MOD
  t *= pow(M-1, N-1-i, MOD)
  t %= MOD
  t *= comb
  t %= MOD
  ans += t
  ans %= MOD
  comb *= N-1-i
  comb %= MOD
  comb *= pow(i+1, MOD-2, MOD)
  comb %= MOD
  
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
MOD = 998244353

N, M, K = map(int, readline().rstrip().split())
fact = [1] * (N+1)
finv = [1] * (N+1)
inv = [1] * (N+1)
inv[0] = 0
for i in range(2, N+1):
    fact[i] = (fact[i-1] * i % MOD)
    inv[i] = (-inv[MOD%i] * (MOD // i)) % MOD
    finv[i] = (finv[i-1] * inv[i]) % MOD

def comb(n, r, mod=MOD):
    if r < 0 or n < r:
        return 0
    return fact[n] * finv[r] * finv[n-r] % mod

def main():
    res = 0
    for k in range(K+1):
        res += comb(N-1, k, MOD) * pow(M-1, N-k-1, MOD) * M
        res %= MOD
    
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
mod=998244353
if m==1:print(0 if k!=n-1 else 1);exit()
fact=[1]*(n-1+1)
inv=[1]*(n-1+1)
for i in range(2,n-1+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n-1,1,-1):
    inv[i-1]=inv[i]*i%mod
ans=0
po=pow(m-1,n-1,mod)*m%mod
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)%mod
for i in range(k+1):
    ans+=ue*inv[n-1-i]%mod*inv[i]%mod*po%mod
    po*=iii
    po%=mod
print(ans%mod)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
mod = 998244353

N = 10 ** 6

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

#階乗計算
kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# コンビネーション計算
def cmb(n, r):
	return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

base = m
ans = 0

for i in range(n-1):
    base = base * (m-1) % mod

for i in range(0, k+1):
    if i == n-1:
        base = m
    ans += base * cmb(n-1, n-1-i)
    ans %= mod
    base = base * inv_t[m-1] % mod

# if m == 1 and k > n-1:
#     print(1)
# else:
print(ans)

Submission status: Accepted

Solution code:
a,b,K=map(int,input().split())
C=998244353
fac=[0]*a #階乗 fac[i]=i!
finv=[0]*a# i!の逆元
inv=[0]*a
N=a-1
def com_init():
	fac[0],finv[0]=1,1
	if a<2:return
	fac[1],finv[1]=1,1
	inv[1]=1
	for i in range(2,N+1):
		fac[i]=fac[i-1]*i%C
		inv[i]=C-inv[C%i]*(C//i)%C#ある数の逆元
		finv[i]=finv[i-1]*inv[i]%C
def com(m,k):
	if m<k: return 0
	elif m<0 or k<0:return 0
	else:
		return fac[m]*(finv[k]*finv[m-k]%C)%C
com_init()
bfac=[0]*a
bfac[0]=1
for i in range(1,a):
  bfac[i]=bfac[i-1]*(b-1) %C
ans=0

for i in range(K+1):
  ans+= com(a-1,i)*bfac[a-1-i]%C
print(ans*b%C)

Submission status: Accepted

Solution code:
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
#

import math
MOD = 998244353
N,M,K = [int(hoge) for hoge in input().split()]
NcK = []#N-1Ck
temp = ModInt(1)
for k in range(K+1):
    NcK.append(temp)
    temp *= N-1-k
    temp /= k+1

if M==1:
    if N==1 or K==N-1:print(1);exit()
    else:print(0);exit()

ans = ModInt(0)
notNcK = ModInt(M*(M-1)**(N-1))
ans += notNcK*NcK[0]
for k in range(K):#M*(M-1)**(N-1-k)*N-1c
    notNcK /= (M-1)
    ans += notNcK*NcK[k+1]
print(ans)

Submission status: Accepted

Solution code:
mod=998244353
fact=[1]
for i in range(1,2*10**5+1):
  fact.append((fact[-1]*i)%mod)
revfact=[1]
for i in range(1,2*10**5+1):
  revfact.append(pow(fact[i],mod-2,mod))
n,m,k=map(int,input().split())
ans=0
for i in range(k,-1,-1):
  group=n-i
  tmp=fact[n-1]*revfact[group-1]*revfact[n-1-(group-1)]
  tmp%=mod
  tmp*=m
  tmp%=mod
  tmp*=pow(m-1,group-1,mod)
  ans+=tmp
  ans%=mod
print(ans)