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:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    MODP = 998244353
    N, M, K = mis()
    if N==1:
        print(M)
        return
    fs = factorials_list(N, MODP)
    invs = invs_list(N, fs, MODP)
    ans = 0
    for k in range(K+1):
        p = k # 前と同じ個数
        q = (N-1) - p #違う個数
        perm = fs[p+q] * invs[p] * invs[q]
        t_ans = perm % MODP
        t_ans *= M
        t_ans %= MODP
        t_ans *= pow(M-1, q, MODP)
        t_ans %= MODP
        ans = (ans + t_ans) % MODP
    print(ans)


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

if __name__ == "__main__":
    p = 998244353
    N = 2 *(10**5)  # 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)
    n = 1
    A = [1]
    ans = 0
    N,M,K = map(int,input().split())
    for i in range(N-1):
        n = n*(M-1)%p
        A.append(n)
    for i in range(K+1):
        a = A[N-1-i]*M % p
        b = cmb(N-1,i,p)
        ans = (ans +(a*b)%p)%p
    print(ans)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
MOD = 998244353
ans = 0
p = 1
px = 1
py = 1
for i in range(k + 1):
    x = m * pow(m - 1, n - 1 - i, MOD) % MOD
    ans += p * x % MOD
    ans %= MOD

    px *= pow(i + 1, MOD - 2, MOD)
    py *= n - i - 1
    px %= MOD
    py %= MOD
    p = px * py % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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


def nCr_mod_p(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 = 998244353
N = 2*10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p), 0! = 1! = 1
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p), 0! = 1! = 1
inv = [0, 1]  # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる

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

ans =0

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

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 and K<N-1:
  print(0)
elif K==N-1:
  print(powmod(M,N))
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:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
# 10 ** 7 might cause MLE
fac = [-1] * (10**6+1)
inv = [-1] * (10**6+1)
finv = [-1] * (10**6+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

mod = 998244353
p = mod

def initNCMMod(limit):
    for i in range(2, limit):
        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 NCMMod(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

initNCMMod(3 * (10**5))
def main():
    n, m, k = LI()
    if m == 1:
        if k >= n-1:
            print(1)
        else:
            print(0)
        return
    m1l = [0] * (n+1)
    m1l[0] = 1
    for i in range(n):
        m1l[i+1] = (m1l[i] * (m-1)) % p
    cnt = 0
    for l in range(k+1):
        x = (m1l[n-l] * m * inv[m-1]) % p
        x *= NCMMod(n-1, l)
        cnt += x
        cnt %= p
    print(cnt % p)




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

comb = Combination(2 * 10 ** 5)

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

    if K == 0:
        ans = pow(M - 1, N - 1, mod) * M
        print(ans % mod)
        return

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



if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD


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

comb = Combination(10 ** 6, MOD)
ans = 0

for i in range(n + 1):
    same_cnt = n - i
    diff_cnt = i + 1
    if same_cnt > k:
        continue
    box = n - 1
    shikiri = box - same_cnt

    tmp = comb.combination(box, shikiri)

    # tmp *= m * ((m - 1)**(shikiri))
    tmp *= m * pow(m - 1, shikiri, MOD)
    
    ans += tmp
    ans %= MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
mod = 998244353
N, M, K = map(int, input().split())
if (M == 1) and (K == (N-1)):
	print(1)
	sys.exit()
def cumprod(x, MOD = mod):
	L = len(x)
	Lsq = int(L**.5 + 1)
	x = np.resize(x, Lsq ** 2).reshape(Lsq, Lsq)
	for n in range(1, Lsq):
		x[:,n] *= x[:,n-1]
		x[:,n] %= MOD
	for n in range(1,Lsq):
		x[n] *= x[n-1, -1]
		x[n] %= MOD
	return x.flatten()[:L]

def make_fact(U, MOD = 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

fact, fact_inv = make_fact(N+10)


ans = 0
D = M * ((M-1) ** (N-1))
D %= mod
for i in range(K+1):
	if i == 0:
		ans += D
	else:
		d = fact[N-1]
		d *= fact_inv[i]
		d %= mod
		d *= fact_inv[N-1-i]
		d %= mod

		tmp = d * D
		tmp %= mod
		ans += tmp

	ans %= mod		
	D *= pow(M-1, mod-2, mod)
	D %= mod

ans %= mod

print(ans)

Submission status: Accepted

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

MOD = 998244353

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

c = [0 for _ in range(n)]
c[0] = 1
for i in range(1, n):
    c[i] = c[i - 1] * (n - i)
    c[i] *= inv(i, MOD)
    c[i] %= MOD
ans = sum([m * c[i] * pow(m - 1, n - 1 - i, MOD) for i in range(k + 1)]) % MOD
print(ans)

Submission status: Accepted

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

mod = 998244353

n, m, k = [int(x) for x in input().split()]

def make_tables(n, mod = 998244353):
    fac = [1, 1] # 階乗テーブル
    finv = [1, 1] #逆元の階乗テーブル
    inv = [0, 1] #逆元テーブル

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

def nCk(n, k, mod = 998244353):
    k = min(k, n-k)
    return fac[n] * finv[k] * finv[n-k] % mod

fac, finv = make_tables(n)
cal = m
ans = 0
for i in range(n - 1 - k):
    cal *= m - 1
    cal %= mod
ans += cal * nCk(n - 1, k)
ans %= mod
for i in range(1, k + 1):
    cal *= (m - 1)
    cal %= mod
    ans += cal * nCk(n - 1, k - i)
    ans %= mod
print(ans)

Submission status: Accepted

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


class Combination:
    """
    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):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        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):
        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


mod = 998244353
total = 0
comb = Combination(n, mod)

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

for i in range(k+1):
    v = comb(n-1, i)
    total += (v * v2[i]) % mod
    total %= mod

print(total)

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
MOD = 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

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) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

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

Submission status: Accepted

Solution code:
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,m,k = map(int,input().split())
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 += (pow(m-1,N-1-i,mod)*cmb(N-1,i,mod))% mod
    ans %= mod
print((m * ans)%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 998244353
INF = float('inf')

class BinomialCoefficient(object):

    def __init__(self, N=210000, MOD=998244353):
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]
        self.MOD = MOD
        for i in range(2, N + 1):
            self.fac.append((self.fac[-1] * i) % MOD)
            self.inv.append((-self.inv[MOD % i] * (MOD // i)) % MOD)
            self.finv.append((self.finv[-1] * self.inv[-1]) % MOD)

    def comb(self, n, r):
        if r < 0 or n < r or r < 0:
            return 0
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.MOD

coef = BinomialCoefficient()

N, M, K = MI()
ans = 0
for l in range(K + 1):
    lans = pow(M - 1, N - l - 1, MOD)
    lans = M * lans % MOD
    lans = lans * coef.comb(N - 1, l) % MOD
    ans = (ans + lans) % MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# MOD = 10**9+7
# MOD = 998244353

NN = 202020
MOD = 998244353

f = [0]*NN
rf = [0]*NN
inv = [0]*NN
f[0], f[1] = 1, 1
rf[0], rf[1] = 1, 1
inv[1] = 1

for i in range(2, NN):
    f[i] = (f[i-1] * i) % MOD
    inv[i] = (-inv[MOD % i] * (MOD // i)) % MOD
    rf[i] = (rf[i-1] * inv[i]) % MOD


def C(n, r):
    return (f[n] * rf[r] * rf[n-r]) % MOD


n, m, k = map(int, input().split())
A = [0]*n
A[0] = m
for i in range(1, n):
    A[i] = (A[i-1]*(m-1))%MOD

# print(A)
ans = 0
for i in range(1, k+2):
    ans = (ans + A[-i]*C(n-1, i-1))%MOD
    # print(A[-i], C(n-1, i-1), A[-i]*C(n-1, i-1), ans)

# print(sum([48,96,72,24,3]))
print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353
class mint:
    def __init__(self, i):
        self.i = i
    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __mul__(self, m):
        return mint(self.i * m.i % MOD)
    def __sub__(self, m):
        t = self.i - m.i
        if t < 0:
            t += MOD
        return mint(t)
    def __pow__(self, m):
        i = self.i
        res = 1
        while(m > 0):
            if m & 1:
                res = res * i % MOD 
            i = i * i % MOD
            m >>= 1
        return mint(res)
    def __truediv__(self, m):
        return mint(self.i * (m ** (MOD - 2)).i % MOD)
    def __repr__(self):
        return repr(self.i)

fact_range = 200005
facts = [1] * (fact_range + 1)
for i in range(0, fact_range):
    facts[i+1] = facts[i] * (i + 1) % MOD

ifacts = [1] * (fact_range + 1)
ifacts[fact_range] = pow(facts[fact_range], MOD - 2, MOD)
for i in range(fact_range, 0, -1):
    ifacts[i-1] = ifacts[i] * i % MOD

def comb(n, k):
    if k < 0 or n < k:
        return mint(0)
    else:
        return mint(facts[n] * ifacts[n-k] % MOD * ifacts[k] % MOD)

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



l = [mint(m) * (mint(m-1) ** (n-1-i)) * comb(n-1, n-1-i) for i in range(n)]
ans = mint(0)
for i in range(k+1):
    ans = ans + l[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

# 階乗、Combinationコンビネーション(numpyを使う)


def cumprod(arr, MOD):
    L = len(arr)
    Lsq = int(L ** 0.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 ** 5) * 2 + 100
fact, fact_inv = make_fact(U, MOD)


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


ans = 0
t = M

if K == (N - 1):
    ans += M

for i in range(1, N):
    kumi = N - i - 1
    t *= M - 1
    t %= MOD
    if K < kumi:
        continue

    c = mod_comb_k(N - 1, i, MOD)
    ans += c * t
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
# mod = 10 ** 9 + 7
mod = 998244353 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def functional(N):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F

D = {}
def inv(a):
    if a in D:
        return D[a]
    
    d = pow(a, mod - 2, mod)
    D[a] = d
    return d


def C(F, a, b):
    return F[a] * inv(F[a - b]) * inv(F[b]) % mod 


def main():
    N, M, K = read_values()
    F = functional(N)
 
    res = 0
    for k in range(K + 1):
        res += M * pow(M - 1, N - 1 - k, mod) * C(F, N - 1, k) % mod
        res %= mod
 
    print(res % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

A = [0]*(K+1)
A[0] = (M*pow(M-1,N-1,mod)) % mod

for i in range(K):
    A[i+1] = (A[i]*(N-1-i)*pow(M-1,mod-2,mod)*pow(i+1,mod-2,mod)) % mod

ans = A[0]
for i in range(K):
    ans = (ans + A[i+1]) % mod

print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
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 = 2
N = 10 ** 6 + 2
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)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



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

                             
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 = 998244353
N = 10 ** 6 + 2
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)





total = 1
for i in range(n):
    total *= m
    total %= p

powm1 = [1]
now = 1
for i in range(3*10**5):
    now *= m-1
    now %= p
    powm1.append(now)

ans = 0
for i in range(k+1):
    parts = n-i
    alloc = cmb(n-1,parts-1,p)
    col = m * powm1[parts-1] % p
    #print(i,alloc,col)
    ans += alloc * col % p
    ans %= p

print(ans)

Submission status: Accepted

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

DIVIDER = 998244353
bit_pow = []
tmp = DIVIDER - 2
while tmp > 0:
    bit_pow.append(tmp % 2)
    tmp >>= 1
N_pow = len(bit_pow)

def myinv(arg):
    global DIVIDER
    ret = 1
    arg_pow = arg
    for i in range(N_pow):
        if bit_pow[i] > 0:
            # print("###", i, arg_pow)
            ret = (ret * arg_pow) % DIVIDER
        arg_pow = (arg_pow * arg_pow) % DIVIDER
    #
    # print("##", arg, '->', ret)
    return ret

def mydiv(a, b):
    b_inv = myinv(b)
    # print("##", a, (b, b_inv))
    ret = (a * b_inv) % DIVIDER
    return ret

tab_comb = [1]
tmp = 1
for i in range(N - 1):
    tmp = (tmp * (N - 1 - i)) % DIVIDER
    tmp = mydiv(tmp, (i + 1))
    tab_comb.append(tmp)
# print("#", tab_comb)

tab_Mpow = [1]
tmp = 1
for i in range(N - 1):
    tmp = (tmp * (M - 1)) % DIVIDER
    tab_Mpow.append(tmp)
# print("#", tab_Mpow)

ans = 0
for i in range(K + 1):
    ans_tmp = M
    ans_tmp = (ans_tmp * tab_comb[i]) % DIVIDER
    ans_tmp = (ans_tmp * tab_Mpow[N - 1 - i]) % DIVIDER
    # print("#", i, ans_tmp)
    ans = (ans + ans_tmp) % DIVIDER

print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)

MOD = 998244353  # type: int

def get_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def make_facts(n):
    '''
        make factorials
        0!(=1), 1!, 2!, 3! .... n!
    '''
    fact = [1]
    for i in range(n):
        fact.append((fact[i] * (i + 1)) % MOD)
    return fact

def make_combs_(n, k):
    '''
        make [C(0, k), C(1, k), C(2, k) ..... C(n, k)]
    '''
    fact = [1] * (n + 1)
    for i in range(2, n + 1):
        fact[i] = (fact[i - 1] * i) % MOD

    ret = [0] * (n + 1)
    for i in range(k, n + 1):
        a = fact[i]
        b = (fact[k] * fact[i - k]) % MOD
        ret[i] = get_fraction_mod(a, b)
    return ret

def make_combs(n, k):
    '''
        make [C(n, 0), C(n, 1), C(n, 2) ..... C(n, k)]
        n! / (n - k)! k!
    '''
    facts = make_facts(n)
    invs = [] # inverted for fraction
    for fact in facts:
        invs.append(pow(fact, MOD - 2, MOD))

    ret = []
    for i in range(0, n + 1):
        a = facts[n]
        #b = facts[i]
        #c = facts[n - i]
        ret.append(a * invs[i] * invs[n - i] % MOD)
    return ret

def solve(N: int, M: int, K: int):
    pows = []
    for i in range(N + 1):
        t = pow(M - 1, i, MOD)
        pows.append(t)
    s = pow(M, N, MOD)
    #s = pows[N]
    coms = make_combs(N - 1, N - 1)
    #print(s, coms)
    for i in range(K + 1, N):
        c = coms[i]
        ss = M * pows[N - i - 1]
        #print(i, c, ss, c * ss)
        s -= c * ss
        s %= MOD
    print(s)
    return

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:
N, M, K = map(int, input().split())
MOD = 998244353

C = [1]
for i in range(N):
    if i == 0:
        C.append(M)
    else:
        C.append((C[i] * (M-1)) % 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 )


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


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

if M == 1:
    if N - 1 <= K:
        print(1)
    else:
        print(0)
elif N == 1:
    print(M)
else:
    print(ans % MOD)

Submission status: Accepted

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


if M>1:
    mod = 998244353
    comb = [1]
    c = 1
    for i in range(N-1):
        c *= N-1-i
        c *= pow(i+1,mod-2,mod)
        c %= mod
        comb.append(c)
    #print(comb)
    M1 = [1]
    m = 1
    for i in range(N):
        m*=M-1
        m%=mod
        M1.append(m)
    #print(M1)
    ans = 0
    #print((M1[N]*M)%mod)
    for i in range(K+1):
        ans += M1[N-1-i]*comb[i]
        ans %= mod
    ans *= M
    ans %= mod
    print(ans)
else:
    if N==K+1:
        print(1)
    else:
        print(0)

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 = 998244353 #出力の制限
N = (10**5)*2+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
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())
mod=998244353

def prepare(m, mod=10 ** 9 + 7):
	fac = [1] * (m + 1)
	inv = [1] * (m + 1)
	for i in range(1, m + 1):
		fac[i] = fac[i - 1] * i % mod
	inv[-1] = pow(fac[-1], mod - 2, mod)
	for i in range(m - 1, -1, -1):
		inv[i] = inv[i + 1] * (i + 1) % mod
	return fac, inv

fac, inv = prepare(n,mod)

def cmb(n, r):
	assert n >= r >= 0
	return fac[n] * inv[n - r] * inv[r] % mod

subt=0
for x in range(k+1,n):
	subt+=cmb(n-1,x)*m%mod*pow(m-1,n-x-1,mod)%mod
	subt%=mod
print((pow(m,n,mod)+mod-subt)%mod)