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:
MODULO = 998244353
n, m, k = map(int, input().split())

facts = [1 for i in range(n+1)]
for i in range(1, n+1):
	facts[i] = (i * facts[i-1]) % MODULO

facts_1 = [pow(facts[i], MODULO-2, MODULO) for i in range(n+1)]

def C(n, k):
	if k > n:
		print("C is 0")
		return 0
	else:
		to_ret = (facts[n] * facts_1[k] * facts_1[n-k]) % MODULO
			# print("C(", n, ", ", k, "): ", to_ret)
		return to_ret

pow_m1 = [pow(m-1, n-i-1,  MODULO) for i in range(0, k+1)]

ans = 0
for pair in range(0, k+1):
	# print("pair", pair)
	choose_pairs = C(n-1, pair)
	# print("choose_pairs", choose_pairs)

	color_blocks = m
	color_blocks *= pow_m1[pair]
	color_blocks %= MODULO
	# print("color_blocks", color_blocks)
	ans += (choose_pairs * color_blocks) % MODULO
	ans %= MODULO
	# print()
print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 998244353
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return ( m + x%m ) % m
    
def nCk(n,k):
    res = 1
    a=n-k
    b=k
    for i in range(1,a+b+1):
        res = res*i%mod
    for i in range(1,a+1):
        res = res*mod_inv(i,mod)%mod
    for i in range(1,b+1):                                 
        res = res*mod_inv(i,mod)%mod
    return res

def main():
    n,m,k = inpm()
    if k == 0:
        print((m*pow(m-1,n-1,mod))%mod)
        return
    if m == 1:
        if n-1 > k:
            print(0)
            return
        print(1)
        return

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

mod = 998244353

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

factorial = [1]
for i in range(1, n):
    factorial.append(factorial[i - 1] * i % mod)

inverseFactorial = [0] * n
inverseFactorial[n - 1] = power(factorial[n - 1], mod - 2)
for i in range(n - 2, -1, -1):
    inverseFactorial[i] = inverseFactorial[i + 1] * (i + 1) % mod

def comb(x, y):
    return factorial[x] * inverseFactorial[y] * inverseFactorial[x - y] % mod



tmp = [m]

for i in range(n):
    t = tmp[-1] * (m - 1) % mod
    tmp.append(t)


ans = 0

for kk in range(k + 1):
    c = comb(n - 1, kk)
    c *= tmp[n - kk - 1]
    ans += c
    ans %= mod

print(ans)

Submission status: Accepted

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

mod = 998244353
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]
for i in range(2, n+1):
    g1.append((g1[-1] * i) % mod)
    inv.append((-inv[mod%i] * (mod//i)) % mod)
    g2.append((g2[-1] * inv[-1]) % mod)

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

ans = 0
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
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

class Comb():
    # class <mint> should be imported
    def __init__(self, n):
        self.n = n
        fact = [0]*(n+1) # 1-indexed
        ifact = [0]*(n+1) # 逆元
        fact[0] = mint(1)
        for i in range(1, n+1):
            fact[i] = fact[i-1]*i
        ifact[-1] = pow(fact[-1], MOD-2)
        for i in range(n, 0, -1):
            ifact[i-1] = ifact[i]*i
        self.fact = fact
        self.ifact = ifact
    def calc(self, n, k):
        if k<0 or k>n:
            return 0
        return self.fact[n]*self.ifact[k]*self.ifact[n-k]

cb = Comb(200005)

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

for i in range(k+1):
    ad = mint(m)
    ad *= pow(m-1,n-1-i,MOD)
    ad *=  cb.calc(n-1,i)
    ans += ad

print(ans)

Submission status: Accepted

Solution code:
class ModCombination:
    def __init__(self,n,m=10**9+7):
        self.num = n
        self.mod = m
        self.f = self.factorials()
        self.g = self.inverse()

    def factorials(self):
        # 0~n!のリスト
        f = [1, 1]
        for i in range(2, self.num + 1):
            f.append(f[-1] * i % self.mod)
        return f

    def inverse(self):
        # 0~n!の逆元のリスト
        g = [1]
        for i in range(self.num):
            g.append(pow(self.f[i + 1], self.mod - 2, self.mod))
        return g

    def combination(self, n, r):
        # nCr mod mを求める
        nCr = self.f[n] * self.g[n - r] * self.g[r]
        nCr %= self.mod
        return nCr

    def permutation(self, n, r):
        # nPr mod mを求める
        nPr = self.f[n] * self.g[n - r]
        nPr %= self.mod
        return nPr

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

a = ModCombination(n,mod)

ans = 0
for i in range(k+1):
    ans += a.combination(n-1,i)*pow(m-1,n-1-i,mod)*m

print(ans%mod)

Submission status: Accepted

Solution code:
MOD = 998244353

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

combination_N_1_ = [1]
for k in range(1, K+1):
    tmp = combination_N_1_[-1] * (N-k) * pow(k, MOD-2, MOD)
    tmp %= MOD
    combination_N_1_.append(tmp)

counter = 0
for i in range(K+1):
    counter += pow(M-1, N-i-1, MOD) * M * combination_N_1_[i]
    counter %= MOD

print(counter)

Submission status: Accepted

Solution code:
def solve():
    MOD = 998244353

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

    # invs[x]: xの逆元 (x:0～n)
    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)

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

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

solve()

Submission status: Accepted

Solution code:
def cmb(n, r):
    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 = 2*10**5+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 )


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)*cmb(n-1,i))%mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353
MOD_t_MAX = 2 * (10**5) + 100
fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        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 MOD_COM(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
def main():
    n, m, k = map(int, input().split())
    MOD_COM_init()
    lim = n-1-k
#    print(lim)
    ans = 0
    for i in range(lim, n):
        x = m * pow(m-1, i, MOD)
        y = MOD_COM(n-1, i)
        z = x*y % MOD
        ans += z
        ans %= MOD
#        print(i, ans)
    print(ans % MOD)

if __name__ == "__main__":
    main()

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 = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

if K==N-1:
    print(pow(M,N,mod))
else:
    S={i:0 for i in range(K+1,N+1)}
    S[K+1]=pow(M,K+1,mod)
    for i in range(K+2,N+1):
        S[i]=M*S[i-1]-M*pow(M-1,i-2-K,mod)*cmb(i-2,K,mod)
        S[i]%=mod
    print(S[N])

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:

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

max_len = n+10  # 適宜変更する
mod = 998244353


def modinv(x):
    '''
    xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
    Python標準のpowは割った余りを出すことも可能。
    '''
    return pow(x, mod-2, mod)


# 二項係数の左側の数字の最大値を max_len　とする。nとかだと他の変数と被りそうなので。
# factori_table = [1, 1, 2, 6, 24, 120, ...] 要は factori_table[n] = n!
# 計算時間はO(max_len * log(mod))
modinv_table = [-1] * (max_len + 1)
modinv_table[0] = None  # 万が一使っていたときにできるだけ早期に原因特定できるようにしたいので、Noneにしておく。
factori_table = [1] * (max_len + 1)
factori_inv_table = [1] * (max_len + 1)
for i in range(1, max_len + 1):
    factori_table[i] = factori_table[i-1] * (i) % mod

modinv_table[1] = 1
for i in range(2, max_len + 1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod
    factori_inv_table[i] = factori_inv_table[i-1] * modinv_table[i] % mod


def binomial_coefficients(n, k):
    '''
    n! / (k! * (n-k)! )
    0 <= k <= nを満たさないときは変な値を返してしまうので、先にNoneを返すことにする。
    場合によっては0のほうが適切かもしれない。
    '''
    if not 0 <= k <= n:
        return None
    return (factori_table[n] * factori_inv_table[k] * factori_inv_table[n-k]) % mod


def binomial_coefficients2(n, k):
    '''
    (n * (n-1) * ... * (n-k+1)) / (1 * 2 * ... * k)
    '''
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans


mod = 998244353

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

print(ans)

Submission status: Accepted

Solution code:
Q = 998244353
def main():
    N, M, K = map( int, input().split())
    ans = 0
    cmb = 1
    for k in range(K+1):
        ans += M*pow(M-1,N-1-k,Q)%Q*cmb%Q
        ans %= Q
        cmb *= (N-k-1)*pow(k+1,Q-2,Q)%Q
        cmb %= Q
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Factorial():
    def __init__(self, n, mod):
        self.mod = mod
        self.fct = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.fct[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.fct[i + 1] = self.fct[i] * (i + 1) % mod
        self.inv[n] = pow(self.fct[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod

    def fact(self, m):
        return self.fct[m]

    def invf(self, m):
        return self.inv[m]

    def perm(self, m, k):
        if m < k: return 0
        return self.fct[m] * self.inv[m - k] % self.mod

    def comb(self, m, k):
        if m < k: return 0
        return self.fct[m] * self.inv[k] * self.inv[m - k] % self.mod

    def hcmb(self, m, k):
        if m + k == 0: return 1
        return self.comb(m + k - 1, k)

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

F = Factorial(max(N, M) + 1, MOD)

res = pow(M, N, MOD)

for i in range(N - 1 - K):
    res -= F.comb(N - 1, i) * M * pow(M - 1, i, MOD)
    res %= MOD

print(res)

Submission status: Accepted

Solution code:
def main():

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

    g1 = [1, 1]
    g2 = [1, 1]
    inv = [0, 1]

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

    def combi(n, r):
      r = min(r, n-r)
      return g1[n]*g2[r]*g2[n-r]%mod

    v = 1
    base = [1, M]
    for i in range(N):
        base.append(base[-1] * (M-1) % mod)

    # print(base)

    ans = 0
    for j in range(K+1):
        v = base[N-j]
        u = combi(N-1, j)
        ans += (v * u) % mod
        ans %= mod
    return ans


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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

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

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] * ifac[com_n - com_r]

md = 998244353

n_max = 200005
fac = [mint(1)]
for i in range(1, n_max + 1): fac.append(fac[-1] * i)
ifac = [mint(1)] * (n_max + 1)
ifac[n_max] /= fac[n_max]
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1)

def main():
    n,m,k=MI()
    ans=mint(0)
    for i in range(k+1):
        ans+=m*pow(m-1,n-1-i,md)*nCr(n-1,i)
    print(ans)

main()

Submission status: Accepted

Solution code:
N,M,K = map(int,input().split())
MOD = 998244353
MAX = 2*(10**5) + 1

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

fac[0],fac[1] = 1,1
finv[0],finv[1] = 1,1
inv[1] = 1
for i in range(2, MAX):
	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):
	if n < k:
		return 0
	if n < 0 or k < 0:
		return 0
	return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

def pow(n, k):
	ans = 1
	while k > 0:
		if k % 2 == 1:
			ans = ans * n % MOD
		n = n * n % MOD
		k = k // 2
	return ans

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

Submission status: Accepted

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

def comb_list(n, r, mod):
    ret = [1]
    for i in range(1, r+1):
        ret.append(ret[-1] * (n+1-i) * pow(i, mod-2, mod) % mod)
    return ret

ans = 0

mod = 998244353

c_list = comb_list(N-1,K,mod)

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

Submission status: Accepted

Solution code:
mod = 998244353

SIZE = 2 * 10 ** 5 + 1
fact = [0] * SIZE
inv = [0] * SIZE
finv = [0] * SIZE
fact[0], fact[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1
for i in range(2, SIZE):
    fact[i] = fact[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod

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


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

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

print(ans)

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

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

Submission status: Accepted

Solution code:
MOD = 998244353
MAXN = 200000+10
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

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

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

for i in range(K+1):
    tmp = M*pow(M-1, N-1-i, MOD)
    ans += comb(N-1, i)*tmp
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    N=2*10**5+3
    mod=998244353
    fac=[1]*(N+1)
    for i in range(1,N+1):
        fac[i]=fac[i-1]*i%mod
    inv_fac=[1]*(N+1)
    inv_fac[N]=pow(fac[N],mod-2,mod)
    for i in range(N-1,0,-1):
        inv_fac[i]=inv_fac[i+1]*(i+1)%mod
    def nCr(n,r):
        if n<0 or r<0 or r>n:
            return 0
        return fac[n]*inv_fac[r]%mod*inv_fac[n-r]%mod
    n,m,k=map(int,input().split())
    m_mod=[1]
    for _ in range(n):
        m_mod.append(m_mod[-1]*(m-1)%mod)
    ans=0
    for i in range(k+1):
        ans_=nCr(n-1,i)*m%mod*m_mod[n-i-1]%mod
        ans=(ans+ans_)%mod
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
pr=998244353
MAX_NUM = 2*10**5 + 5
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
a=0
for i in range(K+1):
    a=(a+M*pow(M-1,N-1-i,pr)*c(N-1,i))%pr
print(a)

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
 #あるかずxのn乗をmodで割ったあまりを返す関数pow_cal(x,n,mod)
def pow_cal(x,n,mod):
    if n==0:
        return 1
    elif n==1:
        return x%mod
    elif n>=2:
        if n%2==0:
            return (pow_cal(x,n//2,mod)**2)%mod
        else:
            return (x*pow_cal(x,n//2,mod)**2)%mod

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_cal(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:
import sys
sys.setrecursionlimit(100000000)
MOD = 998244353
INF = 10 ** 15

MAXN = 200005
factorial = [1]
for i in range(1, MAXN + 1):
    factorial.append(factorial[-1] * i % MOD)

inv_factorial = [-1] * (MAXN + 1)
inv_factorial[-1] = pow(factorial[-1], MOD-2, MOD)
for i in reversed(range(MAXN)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD

def fact(n):
    return factorial[n]%MOD

def nck(n, k):
    if k>n or k<0:
        return 0
    else:
        return factorial[n]*inv_factorial[n - k]*inv_factorial[k]%MOD

def main():  
    N,M,K = map(int,input().split())
    invs = [1]
    for i in range(N + 1):
        invs.append(invs[-1]*pow(M,MOD - 2,MOD)%MOD)

    ans = 0
    for i in range(K + 1):
        ret = nck(N - 1,i)*invs[i]%MOD
        ret *= invs[N - i - 1]*pow(M - 1,N - i - 1,MOD)%MOD
        ans += ret%MOD
        ans %= MOD
    ans *= pow(M,N,MOD)
    ans %= MOD
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
rl = sys.stdin.readline

N,M,K  =Ints()

mod = 998244353


#N = # Combination　における，最大整数部分
#mod = # 大体modで割った余りを求めさせられる．

def make_bikkuri(N):
    bikkuri = [1]
    for i in range(1,N+1):
        bikkuri.append((bikkuri[-1]*i)%mod)
    return bikkuri

bikkuri = make_bikkuri(N)

def nCk(n,k):
    ans = bikkuri[n] * pow(bikkuri[k], mod-2, mod) * pow(bikkuri[n-k], mod-2, mod)
    return ans%mod


ans = 0

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

print(ans)
#print(pow(100-1,))

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 998244353; INF = float("inf")

class Combination(object):
	def __init__(self, N, con):
		self.fac = [0] * (N + 1)
		self.inv = [0] * (N + 1)
		self.finv = [0] * (N + 1)
		self.fac[0], self.fac[1] = 1, 1
		self.inv[1] = 1
		self.finv[0], self.finv[1] = 1, 1

		# 前計算
		for i in range(2, N + 1):
			self.fac[i] = self.fac[i - 1] * i % con
			self.inv[i] = self.inv[con % i] * (con - (con // i)) % con
			self.finv[i] = self.finv[i - 1] * self.inv[i] % con

	def com(self, N, k):
		return (self.fac[N] * self.finv[k] * self.finv[N - k]) % con

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, M, K = getlist()
	if N == 1:
		print(M)
		return

	Com = Combination(N - 1, con)
	ans = 0
	for i in range(N - 1 - K, N):
		ans += Com.com(N - 1, i) * pow(M - 1, i, con)
		ans %= con
	ans *= M
	ans %= con
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

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

class Combination:
    def __init__(self, n, mod):
        self.mod = mod

        # self.fac[i] ≡ i! (factorial:階乗)
        l = [1]
        num = 1
        for i in range(1, n+1):
            num *= i
            num %= mod
            l.append(num)
        self.fac = l.copy()

        # self.rec[i] ≡ 1 / i! (reciprocal:逆数)
        num = pow(num, mod-2, mod)
        l = [1 for i in range(n+1)]
        l[n] = num
        for i in range(n-1, 0, -1):
            num *= i + 1
            num %= mod
            l[i] = num
        self.rec = l.copy()

    # comb(n, r) ≡ nCr
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod

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

print(ans)

Submission status: Accepted

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


def make_fact(n):#0~nの階乗を求める
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i%mod
    return fact
fact = make_fact(N) #＠
def make_fact_inv(n):#0~nの階乗のmodに関する逆元を求める
    fact_inv = [1]*(n+1)
    fact_inv[n] = pow(fact[n], mod-2, mod)#フェルマーの小定理
    for i in range(n, 0, -1):
        fact_inv[i-1] = fact_inv[i]*i%mod
    return fact_inv
fact_inv = make_fact_inv(N)#＠
def comb(n, k):#nCk
    return fact[n]*fact_inv[k]*fact_inv[n-k]%mod

bekizyo = [1] * N

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



ans = 0

for i in range(K + 1):
    ans += comb(N-1, i) * M * bekizyo[N-i-1]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 2 * (10 ** 5) + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

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

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    N, M, K = map(int, input().split())
    mod = 998244353
    c = cmbs(mod)
    r = 0
    for i in range(K+1):
        r += pow(M-1, N-1-i, mod) * c.cmb(N-1, i)
    r *= M
    r %= mod
    return r
print(main())