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:
mod=998244353
def mod_pow(x,n):
    res=1
    while n>0:
        if n&1:
            res=res*x%mod
        x=x*x%mod
        n>>=1
    return res
def inverse_element(t):
    return mod_pow(t,mod-2)

n,m,k=map(int,input().split())
if m==1:
    if k==n-1:
        print(m)
    else:
        print(0)
    exit(0)
ans=0
p1=m*mod_pow(m-1,n-1)%mod
p2=1
for i in range(0,k+1):
    ans+=p1*p2%mod
    ans%=mod
    p1*=inverse_element(m-1)
    p2*=(n-i-1)
    p2*=inverse_element(i+1)
    p1%=mod
    p2%=mod
print(ans%mod)

Submission status: Accepted

Solution code:
def create_array(n: int, r: int, mod, mod2):
    m_ls = [1] * (r + 1)

    for i, j in zip(range(n, 0, -1), range(1, r + 1)):
        m_ls[j] = (m_ls[j - 1] * i * pow(j, mod2, mod)) % mod
    return m_ls


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

    _mod = 998244353
    _mod2 = 998244351

    # res_x = m * ((m-1) ** (n-1-x)) * comb(n-1, x)
    # x:0, 2, ... , k
    # xをk->0とすると(m-1) ** (n-1-x)は少しずつかけていける

    comb_ar = create_array(n-1, k, _mod, _mod2)
    _z = (m - 1) ** (n - 1 - k)
    res = m * _z * comb_ar[k]
    res %= _mod

    if k > 0:
        for x in range(1, k + 1):
            _z *= m - 1
            _z %= _mod
            res += m * _z * comb_ar[k - x]
            res %= _mod

    print(res)


main()

Submission status: Accepted

Solution code:
import math


# class Comb:
#     m_vals = []
#     _mod = 998244353
#
#     def __init__(self, n: int, r: int):
#         m_ls = [(0, 1)] * (r + 1)
#         for i in range(1, r):
#             x = (m_ls[i - 1][0] * self._mod + m_ls[i - 1][1]) * (n - r / r)
#             if x >= self._mod:
#                 m_ls[i] = (int(x // self._mod), int(x % self._mod))
#             else:
#                 m_ls[i] = (0, int(x))
#         self.m_vals = m_ls
#
#     def vv(self, x):
#         return self.m_vals[x][1]

def create_array(n: int, r: int, mod, mod2):
    m_ls = [1] * (r + 1)

    for i, j in zip(range(n, 0, -1), range(1, r + 1)):
        m_ls[j] = (m_ls[j - 1] * i * pow(j, mod2, mod)) % mod
    return m_ls


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

    _mod = 998244353
    _mod2 = 998244351

    # res_x = m * ((m-1) ** (n-1-x)) * comb(n-1, x)
    # x:0, 2, ... , k
    # xをk->0とすると(m-1) ** (n-1-x)は少しずつかけていける

    # com = Comb(n - 1, k)
    comb_ar = create_array(n-1, k, _mod, _mod2)
    _z = (m - 1) ** (n - 1 - k)
    res = m * _z * comb_ar[k]
    res %= _mod

    if k > 0:
        for x in range(1, k + 1):
            _z *= m - 1
            _z %= _mod
            res += m * _z * comb_ar[k - x]
            res %= _mod

    # res %= _mod

    print(res)
    #
    #
    #
    # for x in range(1, k+1):
    #     res += m * (_z * (m-1) ** x) * comb(n-1, x)
    #
    # _a_n = ((m - 1) ** (n - 1 - k)) % _mod
    # _b_n = 1
    # _c_n = 1
    # _d_n = 1
    #
    # _a = [_a_n]
    # _b = [_b_n]
    # # _c = [_c_n]
    # _d = [_d_n]
    # for i in range(1, k + 1):
    #     _a_n *= m - 1
    #     _a_n %= _mod
    #     _a.append(_a_n)
    #     _b_n *= n - i
    #     _b_n %= _mod
    #     _b.append(_b_n)
    #     _c_n *= i
    #     _d_n = (_c_n ** (_mod - 2)) % _mod
    #     _d.append(_d_n)
    #
    # _a.reverse()
    #
    # if k == 0:
    #     res = m * ((m - 1) ** (n - 1))
    #     print(res % _mod)
    # else:
    #     res = (m * ((m - 1) ** (n - 1))) % _mod
    #     for i in range(1, k + 1):
    #         res += (m * _a[i - 1] * _b[i - 1] * _d[i - 1]) % _mod
    #
    #     print(res % _mod)
    #
    # # res_k = m * ((m-1) ** (n-1-k)) * comb(n-1,k)
    # #
    # # for i in range(1, k + 1):
    # #     z_c *= (n-i)
    # #     z_p *= i
    # #     z_c %= _mod
    # #     z_p %= _mod
    # #
    # #     if z_c % z_p == 0:
    # #         comb_ls.append(int(z_c/z_p))
    # #     else:
    # #         for j in range(1, n-1):
    # #             _ = z_c + j * _mod
    # #             if _ % z_p == 0:
    # #                 comb_ls.append(int(_/z_p))
    # #
    # #
    # # comb_ls.reverse()
    # # for i in range(1, k + 1):
    # #     j = k + 1 - i
    # #
    # #     z_before *= (m-1)
    # #     res_x += (m * comb_ls[i-1] * z_before) % 998244353
    # #
    # # print(res_x % _mod)


main()

Submission status: Accepted

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

def init_mod_c(lim=10**6, mod=10**9+7):
    fact = [1, 1] + [0] * (lim-1)
    fact_inv = [1, 1] + [0] * (lim-1)
    inv = [0, 1] + [0] * (lim-1)
    
    for i in range(2, lim+1):
        fact[i] = fact[i-1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        fact_inv[i] = fact_inv[i-1] * inv[i] % mod

    def mod_c(n, m):
        if n < m or n < 0 or m < 0: return 0
        return fact[n] * (fact_inv[m] * fact_inv[n-m] % mod) % mod

    return mod_c

ans = 0
c = init_mod_c(n, MOD)

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

print(ans)

Submission status: Accepted

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

MOD=998244353

ans=0
temp2=1
#temp4=(M-1)**(N-1)%MOD

def getInvs(n, MOD):
  invs = [1] * (n+1)
  for x in range(2, n+1):
    invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
  return invs

invs = getInvs(max(N+3,M-1), MOD)

Vec=[0]*N
#inv=1
#for i in range(MOD-2):
#  inv*=M-1
#  inv%=MOD

'''
for i in range(K+1):
  if i == 0:
    temp1=M
    temp1*=(M-1)**(N-1)%MOD
    temp1%=MOD
    ans+=temp1*temp2%MOD
    #print(cmb)
  else:
    temp1*=invs[M-1]%MOD
    temp2*=(N-i)*invs[i]
    temp2%=MOD
    ans+=temp1*temp2%MOD
    cmb=cmb*(N-i-1)*i*invs[i]%MOD
    #print(cmb)
'''
for i in range(N):
  if i == 0:
    temp1=M
    Vec[N-i-1]=temp1
  else:
    temp1*=(M-1)*(N-i)
    temp1*=invs[i]
    temp1%=MOD
    Vec[N-i-1]=temp1


ans=sum(Vec[:K+1])

print(ans%MOD)

Submission status: Accepted

Solution code:
#左からn個目でendが特定の色の場合に
N,M,K = list(map(int,input().split()))

def xgcd(a, b):
  x0, y0, x1, y1 = 1, 0, 0, 1
  while b != 0:
    q, a, b = a // b, b, a % b
    x0, x1 = x1, x0 - q * x1
    y0, y1 = y1, y0 - q * y1
  return a, x0, y0
def modinv(a, m):
  g, x, y = xgcd(a, m)
  if g != 1:
    raise Exception('modular inverse does not exist')
  else:
    return x % m
def combination(n, k, mod=1e9+7) -> int:
  ret = 1
  for i in range(1, k+1):
    ret = (ret * (n-k+i) * modinv(i, mod))%mod
  return int(ret)

def pow(base, exponent, mod=1e9+7) -> int:
  if exponent == 0:
    return 1
  if exponent > 1:
    d,m = divmod(exponent, 2)
    return (base**m * pow(base, d, mod)**2 ) % mod
  else:
    return base

m = 998244353
res = 0
B = 1
if M != 1:
  mi = modinv(M-1,m)
  A = M * pow(M-1,N-1,m)
  for k in range(K+1):
    if k>0:
      B = (B*(N-k)*modinv(k,m))%m
    res = (res+ A*B)%m
    A = (A*mi)%m
  print (res)
else:
  if K == N-1:
    
    print(1)
  else:
    print(0)

Submission status: Accepted

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

# ---------------------------------------
# nCr(n, r, m) テンプレ
mod = 998244353

fac = [1,1] # 階乗 n!
inv = [0,1] # 逆元 1/n
finv = [1,1] # 逆元の階乗 (n^-1)! = (1/n)!

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

def nCr(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m
# ---------------------------------------

ans = 0
colors = m
for p in range(n-1, -1, -1):
    if p <= k: ans += colors * nCr(n-1, p, mod) % mod
    colors = colors * (m - 1) % mod
ans %= mod
print(ans)

Submission status: Accepted

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

# ---------------------------------------
# nCr(n, r, m) テンプレ
mod = 998244353

fac = [1,1] # 階乗 n!
inv = [0,1] # 逆元 1/n
finv = [1,1] # 逆元の階乗 (n^-1)! = (1/n)!

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

def nCr(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m
# ----------------------------

ans = 0
colors = m
for p in range(n-1, -1, -1):
    if p <= k:
        ans += colors * nCr(n-1, p, mod) % mod
    colors *= m - 1
    colors %= mod
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import os

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

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

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

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

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

    mod=998244353
    ans=0

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

    print(ans%mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

# ---------------------------------------
# nCr(n, r, m) テンプレ
mod = 998244353

fac = [1,1] # 階乗 n!
inv = [0,1] # 逆元 1/n
finv = [1,1] # 逆元の階乗 (n^-1)! = (1/n)!

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

def nCr(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m
# ----------------------------

ans = 0
colors = m
for p in range(n-1, -1, -1):
    if p <= k:
        groups = nCr(n-1, p, mod)
        ans += groups * colors % mod
        ans %= mod
    colors *= m - 1
    colors %= mod
ans += mod
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
#mod = 10**9 + 7
mod=998244353
x=220000
fact=[0 for i in range(x)]
invfact=[0 for i in range(x)]
fact[0]=1

def cmod(n,k,mod):
    if n<0 or n<k:
        return 0
    return (fact[n]*invfact[n-k]*invfact[k])%mod
for i in range(1,x):
    fact[i]=(fact[i-1]*i)%mod
#print(fact)
invfact[-1]=pow(fact[-1],mod-2,mod)
#print(invfact)
for j in range(x-1,0,-1):
    #print(j)
    invfact[j-1]=(invfact[j]*(j))%mod
#print(invfact)

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

for i in range(k+1):
    j=n-i-1
    ans+=(beki[j]*cmod(n-1,i,mod))%mod
    #print(beki[j]*cmod(n-1,i,mod))
print(ans%mod)

Submission status: Accepted

Solution code:
def comb(n,r,m):
    if r == 0: return 1
    return memf[n]*pow(memf[r],m-2,m)*pow(memf[n-r],m-2,m)
def mempow(a,b):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % 998244353
        yield temp
def memfact(a):
    temp = 1
    yield temp
    for i in range(1,a+1):
        temp = temp * i % 998244353
        yield temp

N,M,K = (int(x) for x in input().split())
memp = []
memf = []
mpappend = memp.append
mfappend = memf.append
for x in mempow(M-1,N-1):
    mpappend(x)
for x in memfact(N-1):
    mfappend(x)
ans = 0
if M == 1:
    if K + 1 < N:
        print('0')
    else:
        print('1')
else:
    i = 0
    for i in range(K+1):
        ans = (ans + (comb(N-1,i,998244353)*M*memp[N-i-1])) % 998244353
    print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
import math
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def modmul(a,b):
    return a * b % 998244353
def comb(n,r,m):
    if r == 0: return 1
    return memf[n]*pow(memf[r],m-2,m)*pow(memf[n-r],m-2,m)
def mempow(a,b):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % 998244353
        yield temp
def memfact(a):
    temp = 1
    yield temp
    for i in range(1,a+1):
        temp = temp * i % 998244353
        yield temp

N,M,K = (int(x) for x in input().split())
memp = []
memf = []
mpappend = memp.append
mfappend = memf.append
for x in mempow(M-1,N-1):
    mpappend(x)
for x in memfact(N-1):
    mfappend(x)
ans = 0
if M == 1:
    if K + 1 < N:
        print('0')
    else:
        print('1')
else:
    i = 0
    for i in range(K+1):
        ans = (ans + (comb(N-1,i,998244353)*M*memp[N-i-1])) % 998244353
    print(ans)

Submission status: Accepted

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


#隣り合うブロックN-1
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  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p) 階乗のmod
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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

for i in range(K+1):
    if i==0:
        ans+=(M*pow(M-1,N-1,p)%p)
        ans%=p
    else:
        ans+=cmb(N-1,i,p)*(M*pow(M-1,N-1-i,p)%p)
        ans%=p
print(ans)

Submission status: Accepted

Solution code:
def inverse_mod(a, mod=10**9+7):
    """ Calculate inverse of the integer a modulo mod.
    """
    return pow(a, mod-2, mod)


def combination_mod(n, r, mod=10**9+7):
    """ Calculate nCr modulo mod.
    """

    r = min(r, n-r)
    numerator = denominator = 1
    for i in range(r):
        numerator = numerator * (n - i) % mod
        denominator = denominator * (i + 1) % mod

    return numerator * inverse_mod(denominator, mod) % mod


def create_inverses_table(n, mod=10**9+7):
    """ Create table for inverses of the integers 0 to n modulo mod.
    """

    inv_table = [0] + [1] * n
    for x in range(2, n+1):
        inv_table[x] = -(mod//x) * inv_table[mod % x] % mod

    return inv_table


def solve():
    n_blocks, n_colors, n_max_pairs = map(int, input().split())

    if n_colors == 1:
        return int(n_blocks - n_max_pairs == 1)

    mod = 998244353

    inverses = create_inverses_table(max(n_colors, n_max_pairs), mod)

    e1 = n_colors * pow(n_colors-1, n_blocks-1, mod) % mod
    e2 = 1
    total = e1 * e2

    for k in range(1, n_max_pairs+1):
        e1 = e1 * inverses[n_colors - 1] % mod
        e2 = e2 * (n_blocks - k) * inverses[k] % mod
        total += e1 * e2
        total %= mod

    return total


def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod= 998244353

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

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

Submission status: Accepted

Solution code:
from sys import stdin, stdout

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def binom_tables(n, q):
	fact = [1 for _ in range(n + 1)]
	inv = [1 for _ in range(n + 1)]
	for i in range(1, n+1):
		fact[i] = (fact[i-1] * i) % q
		inv[i] = pow(fact[i], q-2, q)
	return fact, inv

def main():
	MOD = 998244353
	n, m, k = rli()
	F, I = binom_tables(n, MOD)
	
	def binom(n, k, q):
		return (F[n]*((I[k]*I[n-k])%q))%q

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

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def binom_tables(n, q):
	fact = [1 for _ in range(n + 1)]
	inv = [1 for _ in range(n + 1)]
	for i in range(1, n+1):
		fact[i] = (fact[i-1] * i) % q
		inv[i] = pow(fact[i], q-2, q)
	return fact, inv

def binom(n, k, q, F, I):
	return (F[n]*((I[k]*I[n-k])%q))%q

def main():
	MOD = 998244353
	n, m, k = rli()
	F, I = binom_tables(n, MOD)
	ans = 0
	for i in range(n-k, n+1):
		ans += (binom(n-1, i-1, MOD, F, I)*m*pow(m-1, i-1, MOD))%MOD
	print(ans % MOD)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def main():
    mod = 998244353
    fact = [1, 1]
    for i in range(2, 400001):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r):
        return pow(fact[n-r]*fact[r] % mod, mod-2, mod)*fact[n] % mod

    n, m, k = map(int, input().split())
    ans = 0
    for i in range(k+1):
        ans = (ans+m*pow(m-1, n-i-1, mod)*nCr(n-1, n-i-1)) % mod

    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
import math

mod = 998244353

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

N, M, K = map(int, sys.stdin.readline().strip().split())

fact = [1 for i in range(N+1)]
for i in range(1, N):
    fact[i+1] = (fact[i] * (i+1)) % mod

# math.factroialでは速度が足りない
def nCr(n, r, mod=10**9+7):
    if n < 0 or r < 0 or n < r:
        return 0

    if n == 0 or r == 0:
        return 1

    """
    a = math.factorial(n) % mod
    b = math.factorial(r) % mod
    c = math.factorial(n - r) % mod
    """
    a = fact[n]
    b = fact[r]
    c = fact[n-r]

    inv = modinv(b*c, mod)
    ans = a * inv

    return ans % mod


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

print(ans)

Submission status: Accepted

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

mod=998244353

fact=[1 for i in range(N+1)]
for i in range(1,N):
    fact[i+1]=(fact[i]*(i+1))%mod

def nCk(n,k):
    return fact[n]*pow(fact[n-k]*fact[k],mod-2,mod)

result=0
for k in range(K+1):
    result+=nCk(N-1,k)*M*pow(M-1,N-k-1,mod)
    result=int(result)%mod
print(result)

Submission status: Accepted

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

ans = 0
c = 1
for i in range(k + 1):
    ans = (ans + m * pow(m - 1, n - i - 1, MOD) * c) % MOD
    c = (c * (n - 1 - i) * pow(i + 1, MOD - 2, MOD)) % MOD
    # print(f"{ans = }, {c = }")

print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353
n, m, k = map(int, input().split())
c = 1
cnt = 0
for x in range(k + 1):
    cnt += c * m * pow(m - 1, n - 1 - x, MOD) 
    cnt %= MOD
    c *= (n - x - 1) * pow(x + 1, MOD - 2, MOD)
    c %= MOD
print(cnt)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 998244353
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) 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 II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,M,K=LI()
FACT=FLIST(N+M+1)
FINV=[]
for i in FACT: FINV.append(INV(i))
if N == 1:
    print(M)
    exit()
if M == 1:
    if N - 1 == K: print(M)
    else: print(0)
    exit()

res = 0
def ncr(n, r):
    res = 1
    res *= FACT[n]
    res *= FINV[n-r]
    res %= DVSR
    res *= FINV[r]
    res %= DVSR
    return res

for k in range(K+1):
    v = ncr(N-1, k)*M
    v %= DVSR
    v *= POW(M-1, N-1-k)
    v %= DVSR
    res += v

print(res%DVSR)

Submission status: Accepted

Solution code:
def main():
    N, M, K = [int(x) for x in input().split()]
    if M == 1:
        if K == N - 1:
            return 1
        else:
            return 0
    if N == 1:
        return M
    mod = 998244353
    fact = [1]
    for i in range(1, N):
        fact.append(fact[-1] * i % mod)
    count = 0
    for k in range(K + 1):
        current = pow(M - 1, N - k - 1, mod) * M % mod
        rev = pow(fact[k] * fact[N - 1 - k] % mod, mod - 2, mod)
        current = (current * fact[N - 1] % mod) * rev % mod
        count = (count + current) % mod
    return count


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
MOD=998244353
dp=[0] *(k+1)
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 #出力の制限
N = 3*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

ans=0

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)


def binom_preprocess(n, MOD=998244353):
    f = [0 for i in range(n+1)]  # n!
    invf = [0 for i in range(n+1)]  # (n!)^-1
    f[0] = 1
    f[1] = 1
    invf[0] = 1
    invf[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] * i % MOD
        invf[i] = pow(f[i], MOD-2, MOD)
    return f, invf


def binom(n, k, f, invf, MOD=998244353):
    if n < k or n < 0 or k < 0:
        return 0
    else:
        return (f[n] * invf[k] % MOD) * invf[n-k] % MOD


def read():
    N, M, K = map(int, input().strip().split())
    return N, M, K


# 998244353は素数
def solve(N, M, K, MOD=998244353):
    ans = 0
    f, invf = binom_preprocess(N)
    for k in range(K+1):
        ans += binom(N-1, N-k-1, f, invf) * M * pow(M-1, N-k-1, MOD)
        ans %= MOD
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
import math

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

if N == 1:
    print(M)
    exit(0)

mod = 998244353

fac = [0] * N
finv = [0] * N
inv = [0] * N

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

def com(n, k):
    global fac, finv, mod
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod

ans = pow(M, N, mod)
for L in range(K + 1, N):
    result = (M * pow(M - 1, N - L - 1, mod) * com(N - 1, N - L - 1)) % mod
    ans -= result

print(ans % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,M,K=map(int,input().split())
MOD=998244353
 
def comb(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

#https://algo-logic.info/combination/
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
col=M
 
for x in range(N-1,-1,-1):
  now=col*comb(N-1,x,MOD)%MOD
  if x<=K:
    ans = (ans+now)%MOD
  col =col*(M-1)%MOD

print(ans%MOD)

Submission status: Accepted

Solution code:
import numpy as np


class mod_calc():
    def __init__(self, divisor, max_n):
        # assume prime
        self._divisor = divisor
        # nsq = math.ceil(math.sqrt(max_n))
        # feature fix_n? max_k?
        fact = np.empty((max_n+1,), dtype=int)
        fact[1] = fact[0] = f = 1
        for i in range(2, len(fact)):
            f = (f * i) % divisor
            fact[i] = f
        self._fact = fact
        fact_inv = np.empty((max_n+1,), dtype=int)
        fact_inv[max_n] = fi = pow(int(fact[max_n]), divisor-2, divisor)
        for i in range(max_n, 2, -1):
            fi = (fi * i) % divisor
            fact_inv[i-1] = fi
        fact_inv[1] = fact_inv[0] = 1
        self._fact_inv = fact_inv

    def comb(self, n, k):
        k = min(k, n-k)
        if k == 0 or k == n:
            return 1
        return self.mul(self._fact[n], self._fact_inv[n-k], self._fact_inv[k])

    def pow(self, a, n):
        return pow(a, n, self._divisor)

    def mul(self, *a):
        # TODO montogomery
        # https://ikatakos.com/pot/programming_algorithm/number_theory/montgomery_multiplication
        r = a[0]
        for m in a[1:]:
            r = (r * m) % self._divisor
        return r

    def sum(self, *a):
        r = a[0]
        for m in a[1:]:
            r = (r + m) % self._divisor
        return r


def main():
    N, M, K = [int(x) for x in input().split()]
    if M == 1:
        if K == N - 1:
            return 1
        else:
            return 0
    if N == 1:
        return M
    c = mod_calc(998244353, N-1)
    count = 0
    for k in range(K+1):
        count = c.sum(c.mul(c.comb(N-1,k), M, c.pow(M-1, N-k-1)), count)
    return count


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
import math

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

def getInvs(n, MOD):
    invs = [1] * (n+1)
    for x in range(2, n+1):
        invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
    return invs
invs = getInvs(N+3, MOD)

num = M
nums = []
for i in reversed(range(1,N)):
    nums.append(num)
    num *= i*(M-1)
    num *= invs[N-i]
    num %= MOD
nums.append(num)
nums.reverse()

ans = sum(nums[:K+1])
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
##through permutations and combinations we can reduce ans to
##  Summation N-1CK(m-1)^(N-1-K)


import sys
sys.setrecursionlimit(100000000)
DP={}
mod=998244353
product={}
N = 1000001
  
# array to store inverse of 1 to N 
factorialNumInverse = [None] * (N + 1) 
  
# array to precompute inverse of 1! to N! 
naturalNumInverse = [None] * (N + 1) 
  
# array to store factorial of  
# first N numbers 
fact = [None] * (N + 1) 
  
# Function to precompute inverse of numbers 
def InverseofNumber(p): 
    naturalNumInverse[0] = naturalNumInverse[1] = 1
    for i in range(2, N + 1, 1): 
        naturalNumInverse[i] = (naturalNumInverse[p % i] * 
                                   (p - int(p / i)) % p) 
  
# Function to precompute inverse  
# of factorials 
def InverseofFactorial(p): 
    factorialNumInverse[0] = factorialNumInverse[1] = 1
  
    # precompute inverse of natural numbers 
    for i in range(2, N + 1, 1): 
        factorialNumInverse[i] = (naturalNumInverse[i] * 
                                  factorialNumInverse[i - 1]) % p 
  
# Function to calculate factorial of 1 to N 
def factorial(p): 
    fact[0] = 1
  
    # precompute factorials 
    for i in range(1, N + 1): 
        fact[i] = (fact[i - 1] * i) % p 
  
# Function to return nCr % p in O(1) time 
def Binomial(N, R, p): 
      
    # n C r = n!*inverse(r!)*inverse((n-r)!) 
    ans = ((fact[N] * factorialNumInverse[R])% p * 
                      factorialNumInverse[N - R])% p 
    return ans 
def getproduct(M,n):
    #product=(M-1)^n
    global mod,product
    fact=1000
    if n-1 in product:
        product[n]=(M*product[n-1])%mod
        return (M*product[n-1])%mod
    if n<fact:
        return (M**n)%mod
    else:
        Q=int(n/fact)
        R=n%fact
        prev=1
        for q in range(Q):
            prev=(prev*((M**fact)%mod))%mod
        prev=prev*((M**R)%mod)
        product[n]=prev%mod
        return prev%mod
def ncr(n, r, p): 
    # initialize numerator 
    # and denominator 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * pow(den,  
            p - 2, p)) % p 
  
def G(N,M,K):
    global mod
    res=0
    for k in range(K,-1,-1):
        res=(res+((Binomial(N-1,k,mod))%mod *(M*getproduct(M-1,N-k-1))%mod)%mod)%mod
    return res%mod

def F(curr,N,M,K):
    global DP
    if(curr,K) in DP:
        return DP[(curr,K)]
    if curr==N:
        return 1
    if curr==0:
        return M*F(curr+1,N,M,K)
    else:
        a=0
        if K>0:
            a=F(curr+1,N,M,K-1)
        b=(M-1)*F(curr+1,N,M,K)
        DP[(curr,K)]=a+b
        return a+b
N,M,K=map(int,input().strip().split())
InverseofNumber(mod) 
InverseofFactorial(mod) 
factorial(mod) 
#print(F(0,N,M,K)%mod)
print(G(N,M,K))

Submission status: Accepted

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

fac = [1]*(n+1)
inv = [1]*(n+1)
for i in range(1,n+1):
  fac[i] = (fac[i-1]*i) % mod
inv[n] = pow(fac[n], mod-2, mod)
for i in range(n, 0, -1):
  inv[i-1] = (inv[i]*i) % mod
    
def nCr(n,r):  
  if r < 1:
    return 1
  return (((fac[n] * inv[r])%mod) * inv[n-r]) % mod

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

Submission status: Accepted

Solution code:
import sys
l = sys.stdin.readline().strip()
N, M, K = map(int, l.split())
comb_quick = {}
mod = 998244353
C = [1]
for i in range(1, (N-1) // 2 + 1):
    next = C[-1] * (N-i) * pow(i, mod-2, mod)
    C.append(next % mod)
 
res = 0
 
for x in range(K+1):
    crt =  (pow(M-1, N-x-1, mod) * M) % mod 
    crt %= mod
    #print("start")
    idx = min(x, N-1-x)
    crt *= C[idx]
    #print("end")
    crt %= mod
    res += crt
    res %= mod
 
print(res)