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:
class Combination:

    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * \
                modinv[self.mod % i] % self.mod
        return modinv


def resolve():
    n, m, k = map(int, input().split())
    mod = 998244353
    c = Combination(n, mod)
    ans = 0
    for i in range(k + 1):
        ans += c(n - 1, i) * pow(m - 1, n - i - 1, mod)
    ans %= mod
    ans *= m
    ans %= mod
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
MOD = 998244353
fact = [0 for _ in range(n+1)]
fact[1] = m

for i in range(2, n+1):
    fact[i] = fact[i-1] * (m - 1)
    fact[i] %= MOD

class Facts():
    # O(max_num)
    def __init__(self, max_num=2 * 10**5, p=10**9 + 7):
        self.p = p
        self.max_num = max_num
        self.fact = [1] * (self.max_num + 1)
        for i in range(1, self.max_num + 1):
            self.fact[i] = self.fact[i-1] * i
            self.fact[i] %= self.p

    def comb(self, n, k):
        # nCk mod p with memo
        # O(log(p))
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a = self.fact[n]
        b = self.fact[k]
        c = self.fact[n-k]
        return (a*self.power_func(b, self.p-2) *
                self.power_func(c, self.p-2)) % self.p

    def comb_base(self, n, k):
        # nCk mod p w/o memo
        # O(min(n, k)) ?
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a, b = 1, 1
        for i in range(k):
            a *= (n-i)
            a %= MOD
        for i in range(k):
            b *= (k-i)
            b %= MOD
        return (a*self.power_func(b, self.p-2)) % self.p

    def perm(self, n, k):
        # nPk mod p
        # O(log(p))
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a = self.fact[n]
        b = self.fact[n-k]
        return (a * self.power_func(b, self.p-2)) % self.p


    def power_func(self, a, b):
        # a^b mod p
        # O(log(b))
        ans = 1
        while b > 0:
            if b & 1:
                ans = ans * a % self.p
            a = a * a % self.p
            b >>= 1
        return ans


facts = Facts(p=MOD)
ans = 0
for i in range(n-k, n+1):
    if i != n:
        ans += fact[i] * facts.comb(n-1, n-i)
    else:
        ans += fact[i]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m, k = list(map(int, readline().split()))
    MM = 998244353

    ans = 0
    com = 1

    for i in range(k + 1):
        l = n - i
        x = pow(m - 1, l - 1, MM)
        ans += m * x * com
        ans %= MM
        com *= n - (i + 1)
        com *= pow(i + 1, MM - 2, MM)
        com %= MM

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m,k = mi()

mod = 998244353

dp = [0]*n

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

'''
ここは任意
'''
N = 2*(10**5)

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 )

dp[0] = m
for i in range(1,n):
    dp[i] = dp[i-1]*(m-1) % mod

ans = 0
for i in range(k+1):
    tmp = cmb(n-1,i,mod)*dp[n-1-i] % mod
    ans += tmp
    ans %= mod
print(ans)

Submission status: Accepted

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

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % PRIME

PRIME = 998244353
N = 2 * 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % PRIME )
    inverse.append( ( -inverse[PRIME % i] * (PRIME//i) ) % PRIME )
    g2.append( (g2[-1] * inverse[-1]) % PRIME )

ans = 0
for i in range(k + 1):
  ans += cmb(n - 1, i, PRIME) * pow(m - 1, n - i - 1, PRIME) * m
  ans %= PRIME

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    mod = 998244353
    MAX_N = 2 * (10 ** 5)

    fact = [1]
    fact_inv = [0] * (MAX_N + 4)
    for i in range(MAX_N + 3):
        fact.append(fact[-1] * (i + 1) % mod)

    fact_inv[-1] = pow(fact[-1], mod - 2, mod)
    for i in range(MAX_N + 2, -1, -1):
        fact_inv[i] = fact_inv[i + 1] * (i + 1) % mod

    def mod_comb_k(n, k, mod):
        return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod

    n, m, k = map(int, input().split())

    ans = 0
    for i in range(k+1):
        ans += mod_comb_k((n-1), i, mod) * m *pow((m-1), n-i-1, mod)
        ans %= mod
    print(ans)


resolve()

Submission status: Accepted

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

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

fac,ifac=make_tables(998244353,n)



ans=0
for  i in range(k+1):
    #print(cmb(n-1,i,998244353,fac,ifac)*m*pow(m-1,n-1-i,998244353))
    ans+=cmb(n-1,i,998244353,fac,ifac)*m*pow(m-1,n-1-i,998244353)
    ans%=998244353

print(ans)

Submission status: Accepted

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

fact = [1]*(n+1)
rfact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
rfact[n] = r = pow(fact[n], mod-2, mod)
for i in range(n, 0, -1):
  rfact[i-1] = r = r * i % mod

def perm(n, k):
  return fact[n] * rfact[n-k] % mod

def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod

paint = [0]*(n)
ans = 0
for i in range(n-k-1,n):
  ans += comb(n-1,i) * pow(m-1,i,mod)
ans *= m
ans %= mod
print(ans)

Submission status: Accepted

Solution code:

mod = 998244353

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

ans = 0


class Mint(object):
    def cmb(self, n, r, mod: int = 10 ** 9 + 7):
        if (r < 0) or (r > n):
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n - r] % mod

    def cmb_prep(self, N: int, mod: int = 10 ** 9 + 7):
        self.g1 = [1, 1]  # 元テーブル
        self.g2 = [1, 1]  # 逆元テーブル
        inverse = [0, 1]  # 逆元テーブル計算用テーブル

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


mint = Mint()
mint.cmb_prep(N-1, mod)

for k in range(K+1):
    ans += (mint.cmb(N-1, k, mod) * M * pow(M-1, N-k-1, mod)) % mod

print(ans % mod)

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N, M, K = [int(x) for x in input().strip().split()]
    MOD = 998244353
    if M == 1:
        if N == 1:
            print(1)
            exit()
    
    fact = [1] * (N+1)
    inv_fact = [1] * (N+1)
    for i in range(1, N+1):
        fact[i] = ((i) * fact[i-1]) % MOD
    
    inv_fact[-1] = pow(fact[-1], MOD-2, MOD)
    for i in range(N-1):
        inv_fact[N-i-1] = (inv_fact[N-i] * (N - i)) % MOD

    def nCr(n, r):
        if r == 0 or r == n:
            return 1
        r = min(r, n - r)
        return (fact[n] * inv_fact[n-r] * inv_fact[r]) % MOD

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m, k = map(int,input().split())
mod = 998244353
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 2*10**5
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 )

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

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import itertools
import math
n,m,k = ma()
mod = 998244353
nmax = 10**6

fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    for i in range(2,nmax):
        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 ncr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n]* (finv[r] * finv[n-r] %mod) %mod

ncr_pre()
ans = 0
for i in range(k+1):
    ans = ans+ncr(n-1,i) * m*pow(m-1,n-i-1,mod)
    ans %=mod
print(ans)

Submission status: Accepted

Solution code:
def main():
    N,M,K = map(int,input().split())
    MOD = 998244353
    
    if M == 1:
        if K == N-1:
            print(1)
        else:
            print(0)
        exit()
    
    fac = [0]*(N+1)
    fac[0],fac[1] = 1,1
    invfac = [0]*(N+1)
    invfac[0],invfac[1] = 1,1
    
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    invfac[-1] = pow(fac[-1],MOD-2,MOD)
    
    for i in range(N,0,-1):
        invfac[i-1] = (invfac[i]*i)%MOD
    
    def comb(x,y):
        return (fac[x]*invfac[y]*invfac[x-y])%MOD
    
    ans = 0
    base = [1,pow(M-1,N-K-1,MOD)]
    for i in range(K+1):
        base.append((base[-1]*(M-1))%MOD)

    
    for i in range(K+1):
        ret = comb(N-1,i)*(M*base[-i-2])
        ans += ret
    
    print(ans%MOD)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
factorials=[]
current=1
for i in range(n):
  factorials.append(current)
  current=((i+1)*current)%998244353
inverselist=[]
for i in range(n):
  inverselist.append(pow(factorials[i],998244351,998244353))
ans=0
for i in range(0,k+1):
  ans=(ans+m*pow(m-1,n-i-1,998244353)*factorials[n-1]*inverselist[i]*inverselist[n-1-i])%998244353
print(ans)

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 combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - 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 multi_choose(self, n, r):
        """重複組み合わせ nHr """
        return self.combination(n - 1 + r, r)

    def factorial(self, n):
        return self.fact[n]


def main():
    MOD = 998244353

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

    mp = [1]
    t = 1
    for _ in range(N):
        t = t * (M - 1) % MOD
        mp.append(t)

    calc = Calc(max_value=N, mod=MOD)

    ans = mp[N - 1]
    for i in range(1, K + 1):
        ans = (ans + mp[N - 1 - i] * calc.combination(N - 1, i)) % MOD
    ans = ans * M % MOD
    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
#
# sys.setrecursionlimit(10 ** 7)
#
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353

def cmb(k):
    if k < 0 or k > N-1: return 0
    return factN * fact_inv[k] % MOD * fact_inv[N-1-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10 ** 6  # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

# 左からDP
N, M, K = lr()
factN = fact[N-1]
answer = 0
for i in range(K+1):
    answer += cmb(i) * pow((M-1), N-1-i, MOD) % MOD
    answer %= MOD

print(answer * M % MOD)

Submission status: Accepted

Solution code:
max_n=2 * 10**5
mod=998244353
fact, inv_fact = [0] * (max_n + 1), [0] * (max_n + 1)
fact[0] = 1
for i in range(max_n):
    fact[i + 1] = fact[i] * (i + 1) % mod

inv_fact[-1] = pow(fact[-1], mod - 2, mod)
for i in reversed(range(max_n)):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod

def nCr_mod(n, r):
    res = 1
    while n or r:
        a, b = n % mod, r % mod
        if a < b:
            return 0
        res = res * fact[a] % mod * inv_fact[b] % mod * inv_fact[a - b] % mod
        n //= mod
        r //= mod
    return res
n,m,k = map(int,input().split())


mm1 = [1]

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

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

ans = 0
for i in range(k+1):
    if i == 0:
        ans += (mm1[n-1] * m ) % mod
        continue
    if i == n-1:
        ans += (m)
        break
    ans += (mm1[n-1-i] * nCr_mod(n-1,i) * m) % mod

ans = (ans)%mod
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353

def solve():
    def comb(n,k):
        return f[n]*inv[k]*inv[n-k]%mod
    n,m,k = LI()
    if k == 0:
        print(m*pow(m-1,n-1,mod)%mod)
    else:
        f = [1]
        N = 10**6
        for i in range(1,N+1):
            f.append(f[-1]*i%mod)
        inv = [None]*(N+1)
        inv[N] = pow(f[N],mod-2,mod)
        for i in range(N)[::-1]:
            inv[i] = inv[i+1]*(i+1)%mod
        s = m
        dk = m
        p = m-1
        for i in range(n-1):
            s *= m
            s %= mod
            if i >= k:
                s -= dk
                s %= mod
                dk *= m-1
                dk += comb(i,k-1)*m*p%mod
                dk %= mod
                p *= m-1
                p %= mod
        print(s)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

mod=998244353


def do():
    
    def power_func(a,n,p):
        bi=str(format(n,"b"))
        res=1
        for i in range(len(bi)):
            res=(res*res) %p
            if bi[i]=="1":
                res=(res*a) %p
        return res
    
    def cmb(n, r, mod):
        if ( r<0 or r>n ):
            return 0
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod
    
    n,m,k=INTM()
    
    ans=0
    
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    for i in range( 2, n  ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )
    
    for i in range(k+1):
        temp=m
        temp=m*power_func(m-1,n-1-i,mod)%mod
        temp=temp*cmb(n-1,i,mod)%mod
        #print(cmb(n-1,i,mod))
        ans+=temp
        ans=ans%mod
    print(ans)
    
if __name__ == '__main__':
    do()

Submission status: Accepted

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

def modconb(n,k,mod):
    # テーブルを作る
    fac = [0]*(n+1)
    finv = [0]*(n+1)
    inv = [0]*(n+1)  

    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    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
    # 計算
    if n<k: return 0
    if n<0 or k<0: return 0
    
    modcombs = [1]
    for k in range(1,n+1):
        modcombs.append(fac[n]*(finv[k]*finv[n-k]%mod)%mod)
    return modcombs

if n == 1:
    print(m)
    exit()

mods = modconb(n-1,n-1,mod)
cnt = 0
for i in range(k+1):
    cnt += m*mods[i]*pow(m-1,n-i-1,mod)
    cnt %= mod
print(cnt)


# cnt = 100
# for i in range(99):
#     cnt *= 99
#     cnt %= mod

# print(cnt)

Submission status: Accepted

Solution code:


n, m, k = [0] * 3
mod = 998244353

def format_input(filename = None):
	global n, m, k
	if filename == None:
		n, m, k = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(1, 2 * 10**5)
		m = rng(1, 2 * 10**5)
		k = rng(0, n - 1)
		print(n, m, k)

inv_mod = [0, 1]
fact_mod = [1, 1]
inv_fact_mod = [1, 1]
def init_fact_table(n):
	global inv_mod, fact_mod, inv_fact_mod
	for i in range(1, n):
		inv_mod.append((-inv_mod[mod % (i + 1)] * (mod // (i + 1))) % mod)
		fact_mod.append((fact_mod[-1] * (i + 1)) % mod)
		inv_fact_mod.append((inv_fact_mod[-1] * inv_mod[-1]) % mod)

def combin_mod(n, r):
	return (fact_mod[n] * inv_fact_mod[r] * inv_fact_mod[n-r]) % mod

def get_answer():
	init_fact_table(n-1)
	answer = 0
	for i in range(k+1):
		answer += ((m % mod) * pow(m-1, n-i-1, mod)) * combin_mod(n-1, i)
		answer %= mod
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Accepted

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

MOD = 998244353  # type: int


def solve(N: int, M: int, K: int):

    ncomb = [0]*N

    ans = 1
    ncomb[0] = 1
    for i in range(1, N):
        ans *= (N- i) * pow(i,MOD-2,MOD)
        ans %= MOD
        ncomb[i] = ans
    
    answer = 0
    for i in range(K+1):
        answer += M*pow(M-1,N-1-i,MOD)*ncomb[i]
        answer %= MOD
    
    print(answer)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, M, K)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#### 逆元リストいらない
mod = 998244353
fact = [1]
fact_inv = [1]
for i in range(2*10**5+2):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))
def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod
def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
N,M,K = map(int,input().split())
ans = 0
for i in range(K+1):
    X = mod_comb_k(N-1,i,mod)
    Z = power_func(M-1,N-(i+1),mod)
    #print(X,Z)
    ans += X * M * Z % mod
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import math


class Combination:
    def __init__(self, n_max, mod=998244353):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * \
                modinv[self.mod % i] % self.mod
        return modinv


def power_func(a, n, p=998244353):
    bi = str(format(n, "b"))
    res = 1
    for i in range(len(bi)):
        res = (res*res) % p
        if bi[i] == "1":
            res = (res*a) % p
    return res


n, m, k = map(int, input().split())
mod = 998244353
comb = Combination(n)

ans = 0
if n-1 == k:
    ans += m

for i in range(1, n):
    if n-i-1 <= k:
        ans += comb(n-1, i)*m*power_func(m-1, i)
        ans %= mod
print(ans % mod)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
# tmp = m
mod = 998244353
ans = m * pow(m-1, n-1, mod)
ans %= mod
ncm = 1
ncm_list = [0 for _ in range(k)]
for i in range(k):
    ncm *= n-1-i
    ncm *= pow(i+1, mod-2, mod)
    ncm %= mod
    ncm_list[i] = ncm

powm_list = [0 for _ in range(k)]
tmp = m * pow(m-1, n-k-1, mod)
if k != 0:
    powm_list[k-1] = tmp
    for i in range(k-2, -1, -1):
        tmp *= (m-1)
        tmp %= mod
        powm_list[i] = tmp

for i in range(k):
    ans += ncm_list[i] * powm_list[i]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
def power(x, y, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    二分累乗法でx ** yを求める
    
    2 ** n = 4 ** (n//2) = 16 ** (n//4)
    みたいなことをする
    """

    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2, mod)**2 % mod
    else            : return power(x, y//2, mod)**2 * x % mod


def mul(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味したかけ算を行う
    """
    return ((a % mod) * (b % mod)) % mod

def div(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味した割り算を行う    
    """
    if a == b:
        return 1
    return mul(a, inv_t[b], mod)


def factorial_part(start, last, mod):
    """
    startからlastまでのかけ算を行う
    
    factorial_part(2, 4, mod) = 2 * 3 * 4 = 24    
    """
    assert(start <= last)
    x = 1
    for k in range(start, last+1):
        x *= k
        x %= mod
    return x

def combination(n, a, mod):
    if a == 0:
        return 1
    nCa = div(factorial_part(n - a + 1, n, mod), factorial_part(1, a, mod), mod)
    return nCa

n, m, k = list(map(int, input().split()))
mod =  998244353

P = mod
N = max([max([n, m]), k]) + 5
inv_t = [0]+[1]
for i in range(2,N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

powers = [0] * n
a = m
for kk in range(n):
    powers[kk] = a
    a = (a * (m - 1)) % mod

c =0
p = 1
comb = 1
kk = 0
a = n - kk
c += powers[a - 1] * comb

for kk in range(1, k + 1):
    a = n - kk
    comb = (div(comb,  kk, mod) * (a))%mod
    c = c + powers[a - 1] * comb
    c = c%mod
print(c)

Submission status: Accepted

Solution code:

def pow_mod(a, b, m):
    if b == 0:
        return 1
    elif b % 2 == 0:
        d = pow_mod(a, b//2, m)
        return (d * d) % m
    else:
        return (a * pow_mod(a,b-1,m))%m

def comb(n, c, m):
    upe = 1
    dow = 1
    for i in range(1,c+1):
        upe = upe * n % m
        dow = dow * i % m
        n -= 1
    return upe * pow_mod(dow, m-2,m)%m

def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u

MOD = 998244353
def solve(N, M, K):
    MOD = 998244353
    U = N-1-K
    color = M * pow_mod(M-1, U, MOD) % MOD
    c = comb(N-1, U, MOD) % MOD
    #print("c0=%d"%c)
    answer = (c * color) % MOD
    #print("a0", answer)
    #print("U=%d"%U)
    for j in range(N-K, N):
        c = ((c * (N-j)%MOD) * modinv(j, MOD)) % MOD
        #assert c == comb(N-1, j, MOD)
        color = (color * (M-1)) % MOD
        a = (c * color) % MOD
        answer += a
    return answer % MOD
N, M, K = map(int, input().split())
print(solve(N, M, K))