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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect
import functools

MOD = 998244353


def factorial(n, mod=None, memo=False):
    if memo:
        factorial.memo = [1] * (n + 1)
        #print('factorial.memo') # debug
        #print(factorial.memo) # debug
        for i in range(1, n + 1):
            #print('i') # debug
            #print(i) # debug
            if mod is None:
                factorial.memo[i] = i * factorial.memo[i - 1]
            else:
                factorial.memo[i] = i * factorial.memo[i - 1] % mod
            #print('factorial.memo[i]') # debug
            #print(factorial.memo[i]) # debug
    return factorial.memo[n]

def choose(n, r, mod=None):
    a = factorial(n)
    b = factorial(r)
    c = factorial(n - r)
    if mod is None:
        res = a // b // c
    else:
        # fermat's little theorem
        res = a * pow(b, mod - 2, mod) * pow(c, mod - 2, mod) % mod
    return res

def calc(n, m, k):
    res = choose(n - 1, k, MOD) * m * pow(m - 1, n - 1 - k, MOD) % MOD
    #print('res') # debug
    #print(res) # debug
    return res

# in the case k pair is same, pattern is (n-1)Choose(k) * m (m - 1) ** (n - 1 - k)
if __name__ == '__main__':
    n, m, k = list(map(int, input().split()))
    ans = 0
    factorial(n, MOD, True)
    for kk in range(k + 1):
        ans += calc(n, m, kk)
    #print('ans') # debug
    print(ans % MOD)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
n,m,k = 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 = n-1  # 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)

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

Submission status: Accepted

Solution code:
# @author 

import sys

class EColorfulBlocks:
    def solve(self, tc=0):
        import math

        MOD = 998244353

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

        if n == 1:
            print(m)
            return

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

        ans = 0
        p_min = n - k # >= 1
        for p in range(p_min, n + 1):
            ans += m * pow(m - 1, p - 1, MOD) * (c[p])
            ans %= MOD

        # if m >= 2:
        #     for p in range(n + 1 - k, n + 1):
        #         ans += m * pow(m - 1, p - 1, MOD) * (pow(m - 2, p + 1, MOD))
        #         ans %= MOD

        print(ans)



solver = EColorfulBlocks()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
import sys
 
mod = 998244353  # type: int
 
 
class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]  # 階乗を求めるためのキャッシュ
        self.invModulos = [0, 1]  # n^-1のキャッシュ
        self.invFactorial_ = [1, 1]  # (n^-1)!のキャッシュ
 
    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]
 
    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]
 
    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  # To make sure already calculated n^-1
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]
 
 
class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)
 
    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
 
 
def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m
n,m,k=map(int,input().split())
c=Combination(mod)
ans=0
for i in range(k+1):
    ans+=((powm(m-1,n-1-i,mod))*(c.ncr(n-1,i)%mod))%mod
    ans%=mod
m=m%mod
print((ans*m)%mod)

Submission status: Accepted

Solution code:
import math
memo = {}
mod = 998244353
"""
def choose(n,k):
    x = ",".join([str(n),str(k)])
    if x not in memo:
        memo[x] = math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
    return memo[x]
"""
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 = 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)

X,M,K = map(int,input().split())
ans = 0
for k in range(K+1):
    ans += M*pow((M-1),X-k-1,mod)*cmb(X-1,k,mod)

print(ans%mod)

Submission status: Accepted

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
import math
import fractions
import collections
import itertools
import pprint
N,M,K=map(int,input().split())
fracmod=[1]*(2*10**5+10)
invfracmod=[1]*(2*10**5+10)
p=998244353
for i in range(1,2*10**5+10):
    fracmod[i]=(fracmod[i-1]*i)%p
for i in range(2*10**5+10):
    invfracmod[i]=modinv(fracmod[i],p)
ans=0
for i in range(K+1):
    ans=(ans+(M*pow(M-1,N-1-i,p)*fracmod[N-1]*invfracmod[i]*invfracmod[N-1-i])%p)%p
print(ans)

Submission status: Accepted

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

result = 0
p = 998244353
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用


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


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)

for k in range(K + 1):
    c = cmb(N - 1, k, p)
    m = M % p
    n = pow(M - 1, N - k - 1, p)
    result = (result + c * m * n) % p

print(result)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
mod = 998244353
memo = [-1]*(10**6)
memo[0] = 1
def fact(n):
    if memo[n] != -1:
        return memo[n]
    else:
        res = n*fact(n-1)%mod
        memo[n] = res
        return res

def comb(n,k):
    return fact(n)*pow(fact(k),mod-2,mod)*pow(fact(n-k),mod-2,mod)%mod

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

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

Submission status: Accepted

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

mod = 998244353


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


def comb(a, b, p):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = fac[a]
    c *= pow(fac[b], p - 2, p)
    c *= pow(fac[a-b], p - 2, p)
    return c % p


ans = 0
ans += M * pow(M-1, N-1, mod)
ans %= mod

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

print(ans)

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split(' '))
mod = 998244353
ans =0
fac=[0]*(N+1)
inv=[0]*(N+1)
finv=[0]*(N+1)
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,N+1):
    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):
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod
for i in range(K+1):
    ans += M*pow(M-1,N-1-i,mod)*COM(N-1,i)
    ans %=mod
print(ans)

Submission status: Accepted

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

MOD =  998244353
mod = MOD
MAX = N+1
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX
def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[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 cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()

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

ans -= minus 
ans = (ans+MOD)%MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353


class Combination:

    def __init__(self, n, mod):
        self.mod = mod
        self.fact = [1] * (n+1)
        self.ifact = [1] * (n+1)

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

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

    def __call__(self, n: int, k: int):
        return self.get(n, k)


def main():
    N, M, K = [int(x) for x in input().split()]
    comb = Combination(N, MOD)
    ans = 0
    for i in range(0, K+1):
        ans += M * pow(M-1, N-i-1, MOD) * comb(N-1, i)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# Combination
MOD = 998244353
MAX = 2*10**5
fac = [1,1] + [0]*MAX
finv = [1,1] + [0]*MAX
inv = [0,1] + [0]*MAX
for i in range(2,MAX+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

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

N, M, K = map(int, input().split())
ans = 0
for i in range(K+1):
    ans += M*pow(M-1, N-1-i, MOD)*comb(N-1, i)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
#ABC167-E Colorful Blocks
"""
隣り合うブロックの組の個数がi個(i=0~k)であるときの組み合わせ数を求めていく。
まず、k=0の時を考えると、m=4の時、
res = 4*3**(n-1)となることがわかる。
次に、k>0のときは、
どれか2つのブロックを1つにつなぎ合わせると考えて、
res = 4*3**(n-1-i)
これに合わせて、どのブロックが接続するのかを考える必要があり、
どのブロックも右隣のブロックにのみ接続できると考えた場合、
接続できるブロックの個数はn-1個(一番右のブロックは接続先がない)
そこからi個選んで右のブロックにつなぐので、
n-1Ciとなる。
よって、k>0の場合の組み合わせ数は、
res = 4*3**(n-1-i)*(n-1)Ci
となる。
これを for i in range(0,k+1)だけ足し合わせたものが答え。
補足：
例えば3つのブロックを接続すると考えた場合、
2つをつなぎ合わせる場合と区別しそうだが、
「つなぐブロックの個数」はどちらでも同じになる。
更に、その時に全体の分割されたブロックの個数はn-i個で固定されるので、
m*pow(m-1,n-1-i)の部分が変わることもなく、
どの隣のブロックを選ぶかというのも隣接しても不都合がない。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m,k = map(int,readline().split())
mod = 998244353
 
if m == 1:
    if k < n-1:
        print(0)
    else:
        print(1)
    exit()

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

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

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

Submission status: Accepted

Solution code:
from sys import stdin
readline=stdin.readline
N,M,K=map(int,readline().split())
mod=998244353

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

def com(N,K,mod):
    if (K<0) or (N<K):
        return 0
    return fact[N]*finv[K]*finv[N-K]%mod

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

print(ans)

Submission status: Accepted

Solution code:
mod = 998244353
max = (10**5)*2 + 1
facts = [1 for i in range(max)]
invs = [1 for i in range(max)]
 
def inv(x):
    return pow(x,mod-2,mod)
 
for i in range(1,max):
    facts[i] = facts[i-1]*i%mod
    invs[i] = inv(facts[i])
 
def nCk(n,r):
    return facts[n]*invs[r] * invs[n-r] % mod



N, M, K = map(int, input().split())
ans = 0
for i in range(K+1):
    ans += pow(M-1, N-1-i, mod) * nCk(N-1, i)
    ans %= mod
ans *= M
print(ans%mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=998244353
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M,K=map(int,input().split())
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
        fac[0]=fac[1]=1
        finv[0]=finv[1]=1
        inv[1]=1
        for i in range(2,(n+1)):
            fac[i]=fac[i-1]*i%MOD
            inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
            finv[i]=finv[i-1]*inv[i]%MOD
        return fac,finv,inv
    
    fac,finv,inv=COMinit(N+10,MOD)
    
    def COM(n, k, MOD=MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    ans=0
    for i in range(K+1):
        ans+=COM(N-1,i)*M*pow(M-1,N-i-1,MOD)
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 998244353  # type: int


class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]  # 階乗を求めるためのキャッシュ
        self.invModulos = [0, 1]  # n^-1のキャッシュ
        self.invFactorial_ = [1, 1]  # (n^-1)!のキャッシュ

    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  # To make sure already calculated n^-1
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]


class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def choose_k_from_n(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD


def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m

def solve(N: int, M: int, K: int):
    sum = 0
    C = Combination(MOD)
    for i in range(K+1):
        sum = (sum+C.choose_k_from_n(N-1,i)*M*powm(M-1,N-1 - i,MOD))%MOD
    print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
import math
import sys


sys.setrecursionlimit(2000)

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

mod = 998244353
n, m, k = [int(_) for _ in 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 )

# print(g1)
# print(g2)
# print(inverse)

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


print(ans)

# print(pow(2, mod-2, mod))
# print(power(2, mod-2))

Submission status: Accepted

Solution code:
class combination:
    def __init__(self, n, mod):
        fact = [0]*(n+1)
        ifact = [0]*(n+1)
        fact[0] = 1
        for i in range(1, n+1):
            fact[i] = (fact[i-1]*i) % mod
        # 1/n!を逆元で求める
        ifact[n] = pow(fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            ifact[i-1] = (ifact[i]*i) % mod

        self.n = n
        self.mod = mod
        self.fact = fact
        self.ifact = ifact

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


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

ans = 0
for k in range(K+1):
    ncr = c.choose(N-1, k) if k > 0 else 1
    t = ncr*M*pow(M-1, N-k-1, MOD)
    ans = (ans+t) % MOD
print(ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
	'''最大公約数'''
	while b != 0:
		a, b = b, a % b
	return a

def lcm(a, b):
	'''最小公倍数'''
	return (a * b) // gcd(a, b)

def ex_gcd(a, b):
	'''拡張ユークリッドアルゴリズム'''
	x1, x2 = 0, 1
	y1, y2 = 1, 0
	q = 0
	while b != 0:
		x1, x2 = x2, x1 - q * x2
		y1, y2 = y2, y1 - q * y2
		q = a // b
		a, b = b, a % b
	return a, x2, y2

def gcd_n(a, *numbers):
	'''複数の数の最大公約数'''
	d = a
	for b in numbers:
		d = gcd(d, b)
	return d

def lcm_n(a, *numbers):
	'''複数の数の最小公倍数'''
	m = a
	for b in numbers:
		m = lcm(m, b)
	return m

def factorize(n):
	'''素因数分解'''
	factor = 2
	factors = []
	while factor * factor <= n:
		if n % factor == 0:
			count = 1
			n //= factor
			while n % factor == 0:
				n //= factor
				count += 1
			factors.append((factor, count))
		factor += 1
	if n != 1:
		factors.append((n, 1))
	return factors

def totient(n):
	'''オイラーのトーシェント関数'''
	phi = 1
	for prime, count in factorize(n):
		phi *= (prime - 1) * (prime ** (count - 1))
	return phi

def carmichael(n):
	'''カーマイケル関数'''
	prime_carmichaels = [1]
	for prime, count in factorize(n):
		if prime == 2:
			prime_carmichaels.append(count if count <= 2 else (2 ** (count - 2)))
		else:
			prime_carmichaels.append((prime - 1) * (prime ** (count - 1)))
	return lcm_n(*prime_carmichaels)


class Modulo (object):
	def __init__(self, mod):
		self.mod = mod
		self.carmichael = carmichael(mod)
	
	def add(self, x, y):
		return (x + y) % self.mod
	
	def sub(self, x, y):
		return (x - y) % self.mod
	
	def mul(self, x, y):
		return (x * y) % self.mod
	
	def div(self, x, y):
		return self.mul(x, self.inv(y))
	
	def inv(self, x):
		return self.pow(x, self.carmichael - 1)
	
	def pow(self, x, count):
		return pow(x, count, self.mod)


from functools import reduce


MOD = Modulo(998244353)

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

F = [1] * N
for n in range(1, N):
	F[n] = MOD.mul(F[n-1], n)

print(
	reduce(
		MOD.add,
		(
			MOD.mul(
				MOD.div(
					F[N-1],
					MOD.mul(F[k], F[(N-1)-k])
				),
				MOD.mul(
					M,
					MOD.pow(M-1, (N-k)-1)
				)
			)
			for k in range(K+1)
		)
	)
)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
mod = 998244353
f = [1]*(n+1)
revf = [1]*(n+1)
for i in range(2,n+1):
    f[i] = f[i-1] *i%mod
revf[n] = pow(f[n],mod-2,mod)
for i in range(n-1,0,-1):
    revf[i] = revf[i+1]*(i+1)%mod
def C(x,y):return f[x]*revf[y]*revf[x-y]%mod
ans = 0
for i in range(k+1):
    ans += m*pow(m-1,n-i-1,mod)*C(n-1,i)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 998244353
#階乗のリストを作成する
N, M, K = map(int, input().split())
frac = [1]
for i in range(N):
    frac.append(frac[i]*(i+1)%MOD)

#上の公式を用いてcombの計算を行う
def comb(n, k, mod):
    a=frac[n]
    b=frac[k]
    c=frac[n-k]
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
  
def main():
  ans = [0] * (K+1)
  temp = 1
  for i in range(N):
    if i == 0:
      temp*=M
      temp %= MOD
    else:
      temp *= (M-1)
      temp %= MOD
    if i+1 >= N-K:
      ans[i+1-N+K] = temp
  t_ans = 0
  for i in range(len(ans)):
    key = comb(N-1, i, MOD)
    t_ans += (ans[-1-i]*key)
    t_ans %= MOD
  print(t_ans)
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
#互いに素なa,bについて、a*x+b*y=1の一つの解
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
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

import math
MOD = 998244353
N,M,K = [int(hoge) for hoge in input().split()]
NcK = []
POWER = []
cur = 1#Nc0
for k in range(K+1):
    NcK.append(cur)
    cur *= (N-1-k)* mod_inv(k+1,MOD)
    cur %= MOD    

ans = 0
Power = 1
for k in range(N-1-K):#M-1**n-1-K
    Power *= M-1
    Power %= MOD

for k in range(K,-1,-1):
    ans += Power * NcK[k]
        #M-1 ** N-1-k ということは…？
    if k:
        Power *= M-1
        Power %= MOD
    

print((M*ans)%MOD)

Submission status: Accepted

Solution code:
N,M,K = map(int,(input().split()))
MOD = 998244353
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]
 
gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]
 
def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

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

Submission status: Accepted

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

print(ans)

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





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


fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
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)

sum_color = 0
for k in range(K+1):
  num1 = cmb(N-1,k,p)
  num2 = M
  num3 = pow(M-1,N-1-k,p)
  sum_color += (num1*num2*num3)%p
  
print(sum_color%p)

Submission status: Accepted

Solution code:
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 )

def nCr(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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

cmbarr = [1] * N
for r in range(N-1):
    cmbarr[r+1] = cmbarr[r] * (N - 1 - r) * inv[r + 1] % MOD

A = [M*pow(M-1,N-1-i,MOD)*cmbarr[i] % MOD for i in range(K+1)]
print(sum(A) % MOD)

Submission status: Accepted

Solution code:
def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


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

MOD = 998244353
modFacts, invs = prepare(2 * N)
ans = 0
for k in range(K + 1):
    num = N - k
    cnt = 1
    if num >= 0:
        cnt *= modFacts[N - 1] * invs[N - 1 - (num - 1)] * invs[num - 1]
        cnt %= MOD
        cnt *= M * pow(M - 1, num - 1, MOD)
        cnt %= MOD
    ans += cnt
    ans %= MOD

print(ans)