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

fact = [1,1]
finv = [1,1]
inv = [0,1]

for i in range(2,n+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
f = pow(m-1,mod-2,mod) 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

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

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]) % mod)%mod
 
mod = 998244353
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
for i in range(k+1):
    ans += (m * pow(m-1,n-1-i,mod) * cmb(n-1,i,mod)) % mod
print(ans%mod)

Submission status: Accepted

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

p = 998244353
# 何個を同じ色の組にするか0~K
cnt = 0
com = 1
for k in range(K+1):
    l = N-k
    # N-1個の組のうちどれを同じ色にするかN-1Ck
    # それぞれで、N-k個を別の色の順列にする
    # M*(M-1)**(N-k-1)
    x = pow((M-1),(l-1),p)
    cnt += M * x * com
    cnt %= p

    # 次のkのnCk
    com *= N-(k+1)
    com *= pow(k+1,p-2,p)
    com %= p


print(cnt)

Submission status: Accepted

Solution code:
# 二項係数を"やるだけ"にしてくれるライブラリ
from collections import Counter
MAX = 1000005
MOD = 998244353
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()

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

for i in range(K+1):  # つまり没となるブロックの数がi個
    ans += M * pow(M-1, N-(i+1), MOD) % MOD * COM(N-1, i)
print(ans % MOD)

Submission status: Accepted

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

inv_table = [0]+[1]
for i in range(2,K+2):
  inv_table.append(-(MOD//i)*inv_table[MOD%i]%MOD)

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)

if M==1:
  if K<N-1:
    print(0)
  else:
    print(1)
else:
  ans=0
  term1=powmod(M-1,N-1)
  term2=1
  inv_M1=invmod(M-1)
  for i in range(K+1):
    ans+=term1*term2
    ans%=MOD
    term1=term1*inv_M1%MOD
    term2=term2*(N-i-1)*inv_table[i+1]%MOD
    
  answer=M*ans%MOD
  print(answer)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n,r):
    if r >= n:
        return 1
    return fact[n]*pow(fact[n-r], mod-2, mod)*pow(fact[r], mod-2, mod) % mod

n,m,k = LI()
ans = 0
fact = [1]*(max(n,m)+1)
for i in range(1,n):
    fact[i] = i*fact[i-1]
    fact[i] %= mod

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

Submission status: Accepted

Solution code:
mod=998244353


##mod,nについての制約は自分でいかに記入する

def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n,mod):
    #0!からn!までの逆元を素数modで割ったあまりリストを作る関数
    c=1
    uselist=[0 for i in range(n+1)]
    for i in range(1,n+1):
        c*=i
        c%=mod
    first=pow(c,mod-2,mod)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(mod)
    return uselist
    
A=find_power(4*10**5,mod)
B=find_inv_power(4*10**5,mod)

def combi(n,r,mod):
    if n<r:
        return 0
    elif n>=r:
        return (A[n]*B[r]*B[n-r])%(mod)



N,M,K=map(int,input().split())
dp=[0 for i in range(N+1)]
#dp[x]=塗り方でダブりが、ｘ通りになるものの個数
ans=M*pow(M-1,N-1,mod)

for i in range(1,K+1):
    ans+=M*combi(N-1,i,mod)*pow(M-1,N-1-i,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):
    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:
n, m, k = map(int, input().split())
MOD = 998244353

def fn(n, m):
  return (m*pow(m-1, n-1, MOD))%MOD

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, n):
  fact.append((fact[-1]*i) % MOD)
  inv.append((-inv[MOD % i] * (MOD // i) % MOD))
  factinv.append((factinv[-1] * inv[-1]) % MOD)
  
def nCr(n, r):
    return fact[n] * factinv[r] * factinv[n-r] % MOD

ans = fn(n, m)
for i in range(1, k+1):
  ans += nCr(n-1, i)*fn(n-i, m)
  ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,m,k=n1()

def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    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

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

Submission status: Accepted

Solution code:
n,m,k=[int(x) for x in input().split()]
#TODO Mutiply wih m
if m==1:
  if k==n-1: print(1)
  else: print(0)
  exit()
sumi=0
mod=998244353
prodi=pow(m-1,n-1,mod)
invi=pow(m-1,mod-2,mod)
for j in range(n-1,n-1-k-1,-1):
  sumi+=prodi
  sumi%=mod
  prodi*=j
  prodi%=mod
  prodi*=pow(n-j,mod-2,mod)
  prodi%=mod
  prodi*=invi
  prodi%=mod 
sumi*=m
sumi%=mod
print(sumi)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m,k = na()
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
 
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 += pow(m-1,n-i-1,mod)*nCk(n-1,i)

print(ans*m%mod)

Submission status: Accepted

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

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

for i in range( 2, N + 1 ):
    fac.append( ( fac[-1] * i ) % MOD )
    inv.append( ( -inv[MOD % i] * (MOD//i) ) % MOD )
    facinv.append( (facinv[-1] * inv[-1]) % MOD )

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return fac[n] * facinv[r] * facinv[n-r] % MOD

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

print(sum % MOD)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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, readline().split())
mod = 998244353
comb = Combination(n)
ans = 0
n -= 1
for i in range(k + 1):
    ans += comb.calc(n, n - i) * m * pow(m - 1, n - i, mod) % mod
    ans %= mod
print(ans)

Submission status: Accepted

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

mod = 998244353
inv_t = [0]+[1]
inv_te = [0 for i in range(n+1)]
inv_te[0] = 1
inv_te[1] = 1
for i in range(2,n+1):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]
  inv_te[i] = (inv_te[i-1] * inv_t[i]) % mod

n_minus1_mod = 1
for i in range(2,n):
    n_minus1_mod *= i
    n_minus1_mod %= mod

ans = 0

for i in range(k+1):
    ans_plus = (m * pow((m-1), (n-i-1), mod)) % mod
    ans_plus = (ans_plus * n_minus1_mod) % mod
    ans_plus *= inv_te[i]
    ans_plus %= mod
    ans_plus *= inv_te[n-1-i]
    ans_plus %= mod
    ans += ans_plus
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m,k = map(int,readline().split())
mod = 998244353
 
if m == 1:
    if k < n-1:
        print(0)
    else:
        print(1)
    exit()

def pow(n,p,mod=mod): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def factrial_memo(n=2*10**5,mod=mod):
    fact = [1, 1]
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % mod)
    return fact
fact = factrial_memo()

def fermat_cmb(n, r, mod=mod): #needs pow,factrial_memo(only fact). return nCk
    return fact[n] * pow(fact[r],mod-2) * pow(fact[n-r],mod-2) %mod
ans = 0
for i in range(k+1):
    res = m*pow(m-1,n-1-i) #塊を含めて分けられるもの達
    ans += res*fermat_cmb(n-1,i)%mod
print(ans%mod)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
ans = 0
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

mod = 998244353
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 )
for i in range(k + 1):
    ans = (ans + m * pow(m - 1, n - 1 - i, mod) * cmb(n-1,i, mod)) % mod
print(ans)

Submission status: Accepted

Solution code:
def a():
    mod = 998244353
    o = [0] * 63

    def bi(x):
        i = 0
        while x != 0:
            o[i] = x%2
            x //= 2
            i += 1

    bi(mod-2)

    def modinv(m):
        b = 1
        p = m
        for i in range(63):
            if i:
                p = (p * p)%mod
            if o[i]:
                b *= p
                b %= mod
        return b

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

    C = [1]*(K+1)
    for i in range(1,K+1):
        C[i] = (C[i-1] * (N-i) * modinv(i))%mod

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

    ans = 0
    for k in range(0,K+1):
        ans += C[k] * M * M1[N-k-1]
        ans %= mod

    print(ans)

a()

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    # import numpy as np
    import math
    # import random
    input = stdin.readline

    p = 998244353

    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

    # p = 10 ** 9 + 7
    N = 10 ** 6  # N は必要分だけ用意する
    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 pow_k(x, n):
        """
        O(log n)
        """
        if n == 0:
            return 1

        K = 1
        while n > 1:
            if n % 2 != 0:
                K *= x
                K = K%p
            x *= x
            n //= 2

        return (K * x)%p

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

    ans = 0
    first = pow_k(m-1, n-k-1)
    for i in range(k, -1, -1):
        first_cmb = cmb(n-1, i, p)
        ans += (first_cmb*first)%p
        first = (first*(m-1))%p
        # first_cmb = (first_cmb*i)//(n-i)
        


    ans = ans*m
    print(ans%p)

Submission status: Accepted

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

base = 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

mod = 998244353 #出力の制限
N = n
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
rbase = 1
for i in range(n-1-k):
    rbase *= (m-1)
    rbase %= mod

temp = m*rbase
temp %= mod
for i in range(k+1):
    hoge = temp*cmb(n-1,k-i,mod)
    hoge %= mod
    ans += hoge
    temp *= (m-1)
    temp %= mod

print(ans%mod)

Submission status: Accepted

Solution code:
def main():
  mod=998244353
  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] % 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 )

  ans=m*pow(m-1,n-1,mod)
  ans%=mod
  for i in range(1,k+1):
    ans+=(m*pow(m-1,n-1-i,mod))%mod*cmb(n-1,i,mod)
    ans%=mod
  print(ans)
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys


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


MOD = 998244353


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """

    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):
        if n < r:
            return 0
        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(a, n):
    x = 1
    while n:
        if n & 1:
            x = x * a % MOD
        n >>= 1
        a = a * a % MOD
    return x


def main():
    N, M, K = map(int, input().split())
    answer = 0
    combination = Combination(2 * 10 ** 5 + 1, MOD)
    for i in range(K + 1):
        answer += M * power(M - 1, N - i - 1) * combination(N - 1, i) % MOD
    print(answer % MOD)


if __name__ == "__main__":
    main()

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個ばらばら * choose(n-1, n-k-1)

def inv(x):
    e = 1
    for b in bin(modulus - 2)[2:]:
        e *= e
        if b == '1':
            e *= x
        e %= modulus
    return e

pow = [1]  # (m-1) ** i
for i in range(n):
    pow.append(pow[-1] * (m - 1) % 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[n-k-1]
    return x * choose[n-k-1] % modulus

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

Submission status: Accepted

Solution code:
class Factorial():
    def __init__(self, mod=10**9 + 7):
        self.mod = mod
        self._factorial = [1]
        self._size = 1
        self._factorial_inv = [1]
        self._size_inv = 1
    
    def __call__(self, n):
        '''n! % mod '''
        return self.fact(n)
    
    def fact(self, n):
        '''n! % mod '''
        if n >= self.mod:
            return 0
        self.make(n)
        return self._factorial[n]
    
    def fact_inv(self, n):
        '''n!^-1 % mod '''
        if n >= self.mod:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        self.make_inv(n)
        return self._factorial_inv[n]
    
    def comb(self, n, r):
        ''' nCr % mod '''
        if r > n:
            return 0
        t = self.fact_inv(n-r)*self.fact_inv(r) % self.mod
        return self(n)*t % self.mod
    
    def comb_with_repetition(self, n, r):
        ''' nHr % mod '''
        t = self.fact_inv(n-1)*self.fact_inv(r) % self.mod
        return self(n+r-1)*t % self.mod
    
    def perm(self, n, r):
        ''' nPr % mod '''
        if r > n:
            return 0
        return self(n)*self.fact_inv(n-r) % self.mod
    
    def modinv(self, n):
        ''' n^-1 (mod p)'''
        n %= self.mod
        if n == 0:
            raise ValueError('Modinv is not exist! arg={}'.format(n))
        ## TODO better than extend_gcd
        return pow(n, self.mod-2, self.mod)
    
    def make(self, n):
        if n >= self.mod:
            n = self.mod
        if self._size < n+1:
            for i in range(self._size, n+1):
                self._factorial.append(self._factorial[i-1]*i % self.mod)
            self._size = n+1
    
    def make_inv(self, n):
        if n >= self.mod:
            n = self.mod
        self.make(n)
        if self._size_inv < n+1:
            for i in range(self._size_inv, n+1):
                self._factorial_inv.append(self.modinv(self._factorial[i]))
            self._size_inv = n+1


n, m, k = map(int, input().split())
mod = 998244353
comb = Factorial(mod).comb
s = 0
for i in range(k+1, n):
    t = comb(n-1, i) * m
    t %= mod
    t *= pow(m-1, n-1-i, mod)
    t %= mod
    s += t
    s %= mod
ans = pow(m, n, mod) - s
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
mod = 998244353
N,M,K = map(int,input().split())
ans = 0
def color(n,m):
    return m*(pow_k(m-1, n-1))

def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x
            x = x ** 2
            x %= mod
            n = (n - 1) // 2
        else:
            x = x ** 2
            x %= mod
            n = n // 2

    return (K * x)%mod
invs = [0] * (N + 1)
invs[1] = 1
for i in range(2, N + 1):
    invs[i] = mod - invs[mod % i] * (mod//i) % mod
mod_inv_factorials=[1]*(N+1)

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

def mod_factorial(n, m):
    r = 1
    for i in range(1, n+1):
        r *= i
        r %= m
    return r

upper = mod_factorial(N-1,mod)

for i in range(K+1):
    tmp = color(N-i,M)
    ansk = (upper*mod_inv_factorials[i]*mod_inv_factorials[N-1-i]*tmp)%mod
    ans += ansk
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret
N,M,K = map(int,input().split())
MOD=998244353

F=FactMod(N,MOD)
ans=0
for k in range(K+1):
    ans+= M *pow(M-1,N-k-1,MOD)*F.comb(N-1,N-1-k)
    ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class Combination:
    def __init__(self, n: int, mod: int):
        self.mod = mod
        self.fact = [0] * (n + 1)
        self.factinv = [0] * (n + 1)
        self.inv = [0] * (n + 1)
        
        self.fact[0] = self.fact[1] = 1
        self.factinv[0] = self.factinv[1] = 1
        self.inv[1] = 1
        for i in range(2, n + 1):
            self.fact[i] = (self.fact[i - 1] * i) % mod
            self.inv[i] = (-self.inv[mod % i] * (mod // i)) % mod
            self.factinv[i] = (self.factinv[i - 1] * self.inv[i]) % mod
    
    def ncr(self, n: int, r: int):
        if r < 0 or n < r:
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] % self.mod * self.factinv[n - r] % self.mod
    
    def nhr(self, n: int, r: int):
        return self.ncr(n + r - 1, r)
    
    def npr(self, n: int, r: int):
        if r < 0 or n < r:
            return 0
        return self.fact[n] * self.factinv[n - r] % self.mod


def solve():
    N, M, K = map(int, rl().split())
    MOD = 998244353
    
    com = Combination(N + 10, MOD)
    
    ans = 0
    for x in range(K + 1):
        ans = (ans + com.ncr(N - 1, x) * M * pow(M - 1, N - 1 - x, MOD)) % MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
mod = 998244353
# 全て異なる色で塗った場合のリストを作る
d = [0] * (N+1)
d[0] = M
for i in range(N):
    d[i+1] = d[i] * (M-1) % mod

def createFacArr(n, mod):
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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 comb(n ,k, mod, fac, finv):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

fac, finv = createFacArr(N+10, mod)
ans = d[N-1]
#print(d)
for i in range(K):
    ans += d[N-2-i] * comb(N-1, i+1, mod, fac, finv)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
ans = 0
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

mod = 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 )


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

Submission status: Accepted

Solution code:
MOD = 998244353

m = 2*10**5 + 10
fac = [0] * m
finv = [0] * m
inv = [0] * m


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

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

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

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

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

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

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def COMBinitialize(m):
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            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 COMB(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


COMBinitialize(m)


def main():
    N, M, K = (int(i) for i in input().split())
    ans = modint(0)
    for i in range(K+1):
        cur = M*pow(M-1, (N-1-i), MOD)*COMB(N-1, i)
        ans += cur
    print(ans)


if __name__ == '__main__':
    main()

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
    
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x]*pow(fac[y],MOD-2,MOD)*pow(fac[x-y],MOD-2,MOD))%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:
class Combination():
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.fact = self.make_fact(n)
        self.fact_inv = self.make_fact_inv(n)
    def make_fact(self, n):#0~nの階乗を求める
        res = [1]*(n+1)
        for i in range(1, n+1):
            res[i] = res[i-1]*i%self.mod
        return res
    def make_fact_inv(self, n):#0~nの階乗のmodに関する逆元を求める
        fact_inv = [1]*(n+1)
        fact_inv[n] = pow(self.fact[n], self.mod-2, self.mod)#フェルマーの小定理
        for i in range(n, 0, -1):
            fact_inv[i-1] = fact_inv[i]*i%self.mod
        return fact_inv
    def comb(self, m, k):
        return self.fact[m]*self.fact_inv[k]*self.fact_inv[m-k]%self.mod
    


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

#n,m,k = 60522, 114575, 7559
sum_ = 0
comb=Combination(n,lim)
for j in range(k+1):
    ans = m %lim
    #print(m-j-1,n,j)
    ans = (ans *pow(m-1,n-j-1,lim)) % lim
    ans = (ans * comb.comb(n-1,j)) % lim
    #print(ans)
    sum_ = (sum_+ans) % lim
print(sum_)