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:
n,m,k=map(int,input().split())
# 解説動画を見た
mod=998244353
ans=0

#-------------------------------------------------------------------
MAX_N = 10**6

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 
#-------------------------------------------------------------------

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

Submission status: Accepted

Solution code:
mod = 998244353

class Combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod

    def calc(self, n, k):  # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod

n, m, k = map(int, input().split())
C = Combination(n)
ans = 0

for i in range(k+1):
    q = n - i - 1
    tmp = m*pow(m-1, q, mod) * C.calc(n-1, i)%mod
    ans = (ans+tmp)%mod

print(ans)

Submission status: Accepted

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

mod=998244353

# 階乗計算
fact=[0]*(1+n)
fact[0]=1
for i in range(1,n+1):
    fact[i]=fact[i-1]*i % mod
    
# 階乗の逆元計算
invfact=[0]*(1+n)
invfact[-1]=pow(fact[-1],mod-2,mod) # 逆元を計算するのは最後の要素だけでよくてあとは、前に戻りながらかけていく。
for i in range(n-1,-1,-1):
    invfact[i]=invfact[i+1]*(i+1) % mod
    

# 二項係数のリスト化
def cmb(n,r,mod):
    if r<0 or n<r:
        return 0
    return fact[n] * invfact[r] * invfact[n-r] % mod
    
ans=0
for i in range(k+1):
    ans+=(cmb(n-1,i,mod)*m*pow(m-1,n-i-1,mod))%mod
    ans%mod
print(ans%mod)

Submission status: Accepted

Solution code:
mod = 998244353


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

power_cache = {}
power_cache[(M-1, 0)] = 1
for i in range(N-1):
    power_cache[(M-1, i+1)] = (power_cache[(M-1, i)]*(M-1)) % mod


def power(x, y):
    return power_cache[(x, y)]


combination_cache = {}
combination_cache[(N-1, 0)] = 1
for i in range(0, K+1):
    i_plus_inverse = pow(i+1, mod-2, mod)
    combination_cache[(N-1, i+1)] = (combination_cache[(N-1, i)
                                                       ]*(N-1-i)*i_plus_inverse) % mod


def combination(n, r):
    return combination_cache[(n, r)]


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

print(ans)

Submission status: Accepted

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

c = 1

for k in range(K+1):
  out += M * pow(M-1, N-k-1, mod) * c
  out %= mod
  c *= (N-k-1) * pow(k+1, mod-2, mod)
  c %= mod
print(out)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
# from collections import defaultdict

geta = lambda fn: list(map(fn, input().split()))


def egcd(a: int, b: int):
    """
    A solution of ax+by=gcd(a,b). Returns
    (gcd(a,b), (x, y)).
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(a: int, m: int):
    """
    Returns a^{-1} modulo m.
    """
    g, x, y = egcd(a, m)
    if g > 1:
        raise Exception('{}^(-1) mod {} does not exist.'.format(a, m))
    else:
        return x % m


def modpow(a: int, n: int, m: int):
    """
    Returns a^n mod m. (-inf < n < inf)
    """
    if a in [-1, 0, 1]:
        if a == -1:
            return 1 if n & 1 == 0 else m - 1
        else:
            return a

    x, k = (a % m, n) if n >= 0 else (modinv(a, m), -n)

    ret = 1
    while k > 0:
        if k & 1 == 1:
            ret = ret * x % m
        x *= x
        k = k >> 1

    return ret


mod = 998244353

N, M, K = geta(int)

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

a = M * modpow(M - 1, N - 1, mod) % mod
ans, k = a, 1
mi = modinv(M - 1, mod)

for k in range(1, K + 1):
    a = a * (N - k) * mi * modinv(k, mod) % mod
    ans = (ans + a) % mod

print(ans)

Submission status: Accepted

Solution code:
class Facts:
    def __init__(self, mod=10**9+7, n_max=1):
        self.mod     = mod
        self.n_max   = n_max
        self.fact    = [1, 1]
        self.inv     = [0, 1]
        self.factinv = [1, 1]
        if 1 < n_max:
            self.setup_table(n_max)
 
    def cmb(self, n, r):
        if r < 0 or n < r:
            return 0
        if self.n_max < n:
            self.setup_table(n)
        return self.fact[n] * (self.factinv[r] * self.factinv[n-r] % self.mod) % self.mod
 
    def setup_table(self, t):
        for i in range(self.n_max+1,t+1):
            self.fact.append( self.fact[-1] * i % self.mod )
            self.inv.append( -self.inv[self.mod % i] * (self.mod // i) % self.mod )
            self.factinv.append( self.factinv[-1] * self.inv[-1] % self.mod )
        self.n_max = t

# ABC167 E 2020/5/11
MOD = 998244353
 
n, m, k = map(int, input().split())
ans = 0
f = Facts(MOD)

for x in range(k + 1):
    t = (m * pow(m - 1, n - 1 - x, MOD)) % MOD
    ans += f.cmb(n - 1, x) * t % MOD
ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
# E - Colorful Blocks

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

modulus = 998244353

# nブロック m色で塗る → m ** n 通り
# 隣り合うブロックの組 n - 1組のうち 高々k組が同色

# n個ばらばら == m * (m-1) ** (n-1)
# k組同色 == n-k個ばらばら * k個をn-k組に分ける(choose(n-1, n-k-1))

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

choose = [1]  # choose(n-1, i)
for i in range(1, n):
    choose.append(choose[-1] * (n-1-i+1) * inv(i) % modulus)

def solve(n, k):
    x = m * pow(m-1, n-k-1, modulus)
    return x * choose[n-k-1] % modulus

print(sum(solve(n, i) for i in range(k+1)) % modulus)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class Facts:
  def __init__(self, mod=10**9+7, n_max=1):
    self.mod     = mod
    self.n_max   = n_max
    self.fact    = [1, 1]
    self.inv     = [0, 1]
    self.factinv = [1, 1]
    if 1 < n_max:
      setup_table(n_max) 
  
  def cmb(self, n, r):
    if r < 0 or n < r:
      return 0
    if self.n_max < n:
      self.setup_table(n)
    return self.fact[n] * (self.factinv[r] * self.factinv[n-r] % self.mod) % self.mod
  
  def setup_table(self, t):
    for i in range(self.n_max+1,t+1):
      self.fact.append( self.fact[-1] * i % self.mod )
      self.inv.append( -self.inv[self.mod % i] * (self.mod // i) % self.mod )
      self.factinv.append( self.factinv[-1] * self.inv[-1] % self.mod )
    self.n_max = t

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    f=Facts(mod)
    ans=0
    t=m*pow(m-1,n-1-k,mod)
    for kx in range(k,-1,-1):
        ans+=f.cmb(n-1,kx)*t%mod
        t=t*(m-1)%mod
    print(ans%mod)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 998244353
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,K = LI()

    d = [0] * N
    d[0] = M

    for i in range(1,N):
        d[i] = (d[i-1] * (M-1)) % MOD

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def fact(k, mod):
    a = [0] * (k + 1)
    a[0] = 1
    for i in range(1, k + 1):
        a[i] = a[i - 1] * i      
        a[i] = a[i] % mod
    return a
def power(a, n, mod):    
    if n == 0:
        return 1
    if n == 1:
        return a % mod
    if n % 2 == 0:
        return power((a * a) % mod, n // 2, mod) % mod
    else:
        return ((a % mod) * power(a % mod, n - 1, mod)) % mod
def inv(a, mod):
    c = [0] * (len(a))
    for i in range(len(a)):
        c[i] = power(a[i], mod - 2, mod)
    return c
n, m, k = [int(i) for i in input().split()]
mod = 998244353
res = fact(n - 1, mod)
res2 = inv(res, mod)
total = 0
base = power(m - 1, n - 1 - k, mod)
dp = [0] * (k + 1)
dp[0] = base
for i in range(1, k + 1):
    dp[i] = dp[i - 1] * (m - 1)
    dp[i] = dp[i] % mod
for i in range(k + 1):
    fact = (res2[i] * res2[n - 1 - i] * m) % mod
    total += (res[n - 1] * fact * dp[k - i]) % mod
    total = total % mod
print(total)

Submission status: Accepted

Solution code:
n,m,k=(int(i) for i in input().split())
mod = 998244353
fac=[1]
inv=[]
for i in range(n-1):
  fac.append(fac[-1]*(i+2)%mod)
for i in range(n):
  inv.append(pow(fac[i],mod-2,mod))
def modcom(n,k,fac,inv):
  if k>n or k<0:
    return 0
  elif k==n or k==0:
    return 1
  else:
    return((fac[n-1]*inv[k-1]*inv[n-k-1])%mod)
r=0
for i in range(0,k+1):
  r+=(m%mod)*pow(m-1,n-1-i,mod)*modcom(n-1,i,fac,inv)
print(r%mod)

Submission status: Accepted

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
od=998244353
n,k,x=list(map(int,input().split()))

n_c_i=[1]
pow_k=pow(k-1,n,od)
inv_k=pow(k-1,od-2,od)
each_cal=[]
zenpou=[1]
kouhou=[]
for i in range(1,x+1):
    n_c_i.append((n_c_i[-1]*(n-i)*pow(i,od-2,od))%od)
for i in range(n-1):   
    zenpou.append(zenpou[-1]*(k-1)%od)
for i in range(x+1):
    pow_k=pow_k*inv_k%od
    kouhou.append(pow_k)
    each_cal.append(pow(k-1,n-i-1,od))
#zenpou=zenpou[n-x-1:]
zenpou.reverse()
#print(zenpou[0],each_cal[0])
#print(zenpou[-1],each_cal[-1])
#print(len(zenpou))
#print(len(each_cal))
ans=0
for i in range(x+1):
    #each_calのみAC
    #zenpouとkouhouはWA
    #なぜ？
    ans+=(n_c_i[i]*k*zenpou[i])%od
    ans%=od

print(ans)

Submission status: Accepted

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
od=998244353
n,k,x=list(map(int,input().split()))

n_c_i=[1]
pow_k=pow(k-1,n,od)
inv_k=pow(k-1,od-2,od)
each_cal=[]
zenpou=[1]
kouhou=[]
for i in range(1,x+1):
    n_c_i.append((n_c_i[-1]*(n-i)*pow(i,od-2,od))%od)
for i in range(n-1):   
    zenpou.append(zenpou[-1]*(k-1)%od)
for i in range(x+1):
    pow_k=pow_k*inv_k%od
    kouhou.append(pow_k)
    each_cal.append(pow(k-1,n-i-1,od))
zenpou=zenpou[n-x-1:]
zenpou.reverse()
#print(zenpou[0],each_cal[0])
#print(zenpou[-1],each_cal[-1])
#print(len(zenpou))
#print(len(each_cal))
ans=0
for i in range(x+1):
    #each_calのみAC
    #zenpouとkouhouはWA
    #なぜ？
    ans+=(n_c_i[i]*k*zenpou[i])%od
    ans%=od

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple

MODULO = 998244353


def combi(n: int, k: int, fact: List[int]) -> int:
    r = 1
    for i in range(k):
        r *= n - i
    return (r // fact[k]) % MODULO


def factorial(n: int) -> List[int]:
    fact = [0] * (n + 1)
    inv = [0] * (n + 1)
    fact[0] = 1
    inv[0] = 1
    for i in range(1, n + 1):
        fact[i] = (i * fact[i - 1]) % MODULO
        inv[i] = pow(fact[i], MODULO - 2, MODULO)
    return fact, inv


def solve(n: int, m: int, k: int) -> int:
    result = 0
    # fill the cache
    fact, inv = factorial(n - 1)
    for i in range(k + 1):
        result = (
            result
            + (
                m
                * pow(m - 1, n - i - 1, MODULO)
                * fact[n - 1]
                * inv[i]
                * inv[n - 1 - i]
            )
        ) % MODULO
    return result


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N, M, K = map(int, input().split())
    result = solve(N, M, K)
    print(result)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Accepted

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
od=998244353
n,k,x=list(map(int,input().split()))

n_c_i=[1]
pow_k=pow(k-1,n,od)
inv_k=pow(k-1,od-2,od)
each_cal=[]
zenpou=[1]
kouhou=[]
for i in range(1,x+1):
    n_c_i.append((n_c_i[-1]*(n-i)*pow(i,od-2,od))%od)
for i in range(n-1):    
    zenpou.append(zenpou[-1]*(k-1)%od)
for i in range(x+1):
    pow_k=pow_k*inv_k%od
    kouhou.append(pow_k)
    each_cal.append(pow(k-1,n-i-1,od))

zenpou.reverse()
ans=0
for i in range(x+1):
    #each_calのみAC
    #zenpouとkouhouはWA
    #なぜ？
    ans+=(n_c_i[i]*k*each_cal[i])%od
    ans%=od

print(ans)

Submission status: Accepted

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
od=998244353
n,k,x=list(map(int,input().split()))

n_c_i=[1]
pow_k=pow(k-1,n,od)
inv_k=pow(k-1,od-2,od)
each_cal=[]
zenpou=[1]
kouhou=[]
for i in range(1,x+1):
    n_c_i.append((n_c_i[-1]*(n-i)*pow(i,od-2,od))%od)
    zenpou.append(zenpou[-1]*(k-1)%od)
for i in range(x+1):
    pow_k=pow_k*inv_k%od
    kouhou.append(pow_k)
    each_cal.append(pow(k-1,n-i-1,od))
    

ans=0
for i in range(x+1):
    #ans+=comb*k*pow_k%od
    ans+=(n_c_i[i]*k*each_cal[i])%od
    ans%=od

print(ans)

Submission status: Accepted

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**6)
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
od=998244353
n,k,x=list(map(int,input().split()))

n_c_i=[1]
for i in range(1,x+1):
    n_c_i.append((n_c_i[-1]*(n-i)*pow(i,od-2,od))%od)
#print(n_c_i)
pow_k=pow(k-1,n-1,od)
inv_k=pow(k-1,od-2,od)
ans=0
#print(ans)
for i in range(x+1):
        
    #pow_k=(pow_k*inv_k)%od
    p_k=(k*pow(k-1,n-i-1,od))%od
    #ans+=comb*k*pow_k%od
    ans+=(n_c_i[i]*p_k)%od
    ans%=od

print(ans)

Submission status: Accepted

Solution code:
def pre_c(n, mod):
    f = [0] * (n + 1)
    g = [0] * (n + 1)
    for i in range(n + 1):
        if i == 0:
            f[i] = 1
            g[i] = 1
        else:
            f[i] = (f[i - 1] * i) % mod
            g[i] = pow(f[i], mod - 2, mod)

    return f, g
n, m, k = map(int,input().split())
mod = 998244353
F, G = pre_c(n - 1, mod)
cnt = 0
for i in range(k + 1):
    temp = F[n - 1] * G[i] * G[n - 1 - i] * m * pow(m - 1, n - 1 - i, mod)
    cnt = (cnt + temp) % mod
print(cnt)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    a = []
    b = []
    d = [1, 1]
    e = [1, 1]
    f = [0, 1]
    for i in range(2, n):
        d.append(d[-1]*i%z)
        f.append((-f[z%i]*(z//i))%z)
        e.append(e[-1]*f[-1]%z)
    for i in range(k+1):
        b.append(d[n-1]*e[i]*e[n-i-1]%z)
    x = 0
    g = [1]
    for i in range(n-1):
        g.append(g[i]*(m-1)%z)
    for i in range(k+1):
        a.append(b[i]*m*g[n-i-1]%z)
    for i in range(k+1):
        x = (x+a[i])%z
    print(x)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 998244353

def make_array_for_comb(N, mod):
    fact = [1,1]
    fact_inv = [1,1]
    inv = [0,1]
    for i in range(2, N+1):
        fact.append((fact[-1]*i) % mod)
        inv.append((-inv[mod%i] * (mod//i)) % mod)
        fact_inv.append((fact_inv[-1]*inv[i]) % mod)
    return fact, fact_inv

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

n,m,k = map(int,readline().split())
fact, fact_inv = make_array_for_comb(n,mod)
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
class Facts:

  def __init__(self, mod=10**9+7, n_max=1):
    self.mod     = mod
    self.n_max   = n_max
    self.fact    = [1, 1]
    self.inv     = [0, 1]
    self.factinv = [1, 1]
    if 1 < n_max:
      self.setup_table(n_max)

  def cmb(self, n, r):
    if r < 0 or n < r:
      return 0
    if self.n_max < n:
      self.setup_table(n)
    return self.fact[n] * (self.factinv[r] * self.factinv[n-r] % self.mod) % self.mod

  def setup_table(self, t):
    for i in range(self.n_max+1,t+1):
      self.fact.append( self.fact[-1] * i % self.mod )
      self.inv.append( -self.inv[mod % i] * (self.mod // i) % self.mod )
      self.factinv.append( self.factinv[-1] * self.inv[-1] % self.mod )
    self.n_max = t

# ABC167 E 2020/5/11
mod = 998244353

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

ans = 0
f = Facts(mod)
t = m * pow(m-1, n-1-k, mod)

for i in range(k,-1,-1):
  ans += f.cmb(n-1,i) * t % mod
  t = t * (m-1) % mod

print(ans % mod)

Submission status: Accepted

Solution code:
class Facts:
  
  def __init__(self, mod=10**9+7, n_max=1):
    self.mod     = mod
    self.n_max   = n_max
    self.fact    = [1, 1]
    self.inv     = [0, 1]
    self.factinv = [1, 1]
    if 1 < n_max:
      setup_table(n_max) 
  
  def cmb(self, n, r):
    if r < 0 or n < r:
      return 0
    if self.n_max < n:
      self.setup_table(n)
    return self.fact[n] * (self.factinv[r] * self.factinv[n-r] % self.mod) % self.mod
  
  def setup_table(self, t):
    for i in range(self.n_max+1,t+1):
      self.fact.append( self.fact[-1] * i % self.mod )
      self.inv.append( -self.inv[mod % i] * (self.mod // i) % self.mod )
      self.factinv.append( self.factinv[-1] * self.inv[-1] % self.mod )
    self.n_max = t

mod = 998244353

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

ans = 0
f = Facts(mod)
t = m * pow(m-1, n-1-k, mod)

for i in range(k,-1,-1):
  ans += f.cmb(n-1,i) * t % mod
  t = t * (m-1) % mod

print(ans % mod)

Submission status: Accepted

Solution code:
class Facts:
  
  def __init__(self, mod=10**9+7, n_max=1):
    self.mod     = mod
    self.n_max   = n_max
    self.fact    = [1, 1]
    self.inv     = [0, 1]
    self.factinv = [1, 1]
    if 1 < n_max:
      setup_table(n_max) 
  
  def cmb(self, n, r):
    if r < 0 or n < r:
      return 0
    if self.n_max < n:
      self.setup_table(n)
    return self.fact[n] * (self.factinv[r] * self.factinv[n-r] % self.mod) % self.mod
  
  def setup_table(self, t):
    for i in range(self.n_max+1,t+1):
      self.fact.append( self.fact[-1] * i % self.mod )
      self.inv.append( -self.inv[mod % i] * (mod // i) % self.mod )
      self.factinv.append( self.factinv[-1] * self.inv[-1] % self.mod )
    self.n_max = t

mod = 998244353

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

ans = 0
f = Facts(mod)
t = m * pow(m-1, n-1-k, mod)

for i in range(k,-1,-1):
  ans += f.cmb(n-1,i) * t % mod
  t = t * (m-1) % mod

print(ans % mod)

Submission status: Accepted

Solution code:
MOD = 998244353
FACT_MAX = 2 * 10 ** 5
fact = [1] * FACT_MAX
for i in range(1, FACT_MAX):
    fact[i] = fact[i - 1] * i % MOD
def comb(n, r):
    return fact[n] * pow(fact[n - r], MOD - 2, MOD) * pow(fact[r], MOD - 2, MOD) % MOD
N, M, K = map(int, input().split())
total = 0
for k in range(K + 1):
    total = (total + comb(N - 1, k) * M * pow(M - 1, N - k - 1, MOD)) % MOD
print(total)

Submission status: Accepted

Solution code:
import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


class Comb(object):

    def __init__(self, n, MOD=1e9 + 7):
        self.MOD = MOD

        self.fact = [1, 1] + [0] * n
        self.finv = [1, 1] + [0] * n
        self.inv = [0, 1] + [0] * n

        for i in range(2, n + 2):
            self.fact[i] = self.fact[i - 1] * i % self.MOD
            self.inv[i] = -self.inv[self.MOD % i] * (self.MOD // i) % self.MOD
            self.finv[i] = self.finv[i - 1] * self.inv[i] % self.MOD

    def calc_p(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        return self.fact[n] * self.finv[n - k] % self.MOD

    def calc_c(self, n, k):
        if n < k or n < 0 or k < 0:
            return 0
        return self.fact[n] * (self.finv[k] * self.finv[n - k] %
                               self.MOD) % self.MOD

    def calc_h(self, n, k):
        return self.calc_c(n + k - 1, n - 1)


MOD = 998244353
N, M, K = map(int, read().split())
comb = Comb(N + K, MOD=MOD)

ans = 0
col = M

for x in range(N - 1, -1, -1):
    acc = col
    acc *= comb.calc_c(N - 1, x)
    if x <= K:
        ans += acc
        ans %= MOD
    col *= (M - 1)
    col %= MOD

print(ans)

Submission status: Accepted

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

    fact, finv = [1] * N, [1] * N
    for i in range(1, N):
        fact[i] = fact[i - 1] * i % MOD

    finv[N - 1] = pow(fact[N - 1], MOD - 2, MOD)
    for i in range(N - 2, -1, -1):
        finv[i] = finv[i + 1] * (i + 1) % MOD

    def C(n, r):
        return fact[n] * finv[r] * finv[n - r] % MOD

    ans = pow(m, n, MOD)
    for r in range(1, n - k):
        ans -= C(n - 1, r - 1) * m * pow(m - 1, r - 1, MOD)
        ans %= MOD

    print(ans)

main()

Submission status: Accepted

Solution code:
mod = 998244353

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

comb = 1
for i in range(k + 1):
  tmp = comb * m * pow(m-1, n-i-1, mod) % mod
  count = (count + tmp) % mod
  comb = comb * (n - i - 1) * pow(i+1, mod-2, mod) % mod
print(count)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
mod = 998244353
s = m - 1
S = 1
ans = 0
fact = [1] * (n + 1)
fact_inv = [0] * (n + 1)
for i in range(1, n + 1):
	fact[i] = (fact[i - 1] * i) % mod
	fact_inv[i] = pow(fact[i], mod - 2, mod)
fact_inv[0] = fact_inv[1]

#k += 1
for t in range(n):
	if t >= n - k - 1:
		b = fact[n - 1] * fact_inv[t] * fact_inv[n - t - 1]
		ans += (S * b) % mod
		#print(t, S, b % mod)
	S = (S * s) % mod
	
print((m * ans) % mod)

Submission status: Accepted

Solution code:
import math
n,m,k=map(int,input().split())
num=210000
mod=998244353
fact=[0]*num
invfact=[0]*num
fact[0]=1
for i in range(1,num):
    fact[i]=fact[i-1]*i%mod
invfact[num-1]=pow(fact[num-1],mod-2,mod)
for i in range(num-2,-1,-1):
    invfact[i]=invfact[i+1]*(i+1)%mod
def nck(n,k):
    if n<k or k<0:
        return 0
    return fact[n]*invfact[k]*invfact[n-k]
ans=0
for i in range(k+1):
    #print(nck(n-1,i)*m*pow(m-1,n-i-1,mod)%mod)
    ans+=nck(n-1,i)*m*pow(m-1,n-i-1,mod)%mod
    ans%=mod
print(ans)

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

    if M == 1:
        if K == N - 1:
            print(1)
        else:
            print(0)
        exit()
    
    prepare(N + 10, MOD)

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

        m *= m_inv
        m %= MOD

    print(ans * M % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

class ModCombination():
    def __init__(self, n, mod=998244353):
        self.mod = mod
        self.N = n
        fact = [1, 1] # 元テーブル
        ifact = [1, 1] #逆元テーブル
        inverse = [0, 1] #逆元テーブル計算用テーブル

        for i in range( 2, n + 1 ):
            fact.append( ( fact[-1] * i ) % mod )
            inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
            ifact.append( (ifact[-1] * inverse[-1]) % mod )
        
        self.fact = fact
        self.ifact = ifact
        self.inverse = inverse

    def nCr(self, n, r):
        if r < 0 or r > n:
            return 0
        return self.fact[n] * self.ifact[r] * self.ifact[n-r] % self.mod

    def nPr(self, n, r):
        if r < 0 or r > n:
            return 0
        return self.fact[n] * self.ifact[n-r] % self.mod

def main():
    N, M, K = map(int, input().split())
    MOD = 998244353
    mc = ModCombination(N, MOD)

    ans = 0
    for i in range(0, K + 1):
        # N-i個のボールを隣り合う色が必ず異なるようにする並べ方
        # 最初はM通り、それ以降は前の色とは違うM-1通り
        # = M * (M - 1) * (M - 1) * ... = M * (M - 1)^(N - i - 1)
        base = M * pow(M - 1, N - i - 1, MOD)
        # 同じ色のボールを追加する場所をi箇所選ぶ
        # = 最初以外の N - 1箇所から、「前の色と同じ」を設定する場所をi箇所選ぶ
        # = nCr(N - 1, i)
        patterns = base * mc.nCr(N - 1, i)
        # print(i, base, mc.nCr(N - 1, i, mod), patterns)
        
        ans = (ans + patterns) % MOD
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

# 0^0 = 1

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

    MOD = 998244353

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

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

    print(ans * M % MOD)


if __name__ == "__main__":
    main()