Problem:


Score : 500 points

Problem Statement

There are N blocks arranged in a row. Let us paint these blocks.

We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.

Find the number of ways to paint the blocks under the following conditions:

For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.

There may be at most K pairs of adjacent blocks that are painted in the same color.

Since the count may be enormous, print it modulo 998244353.

Constraints

All values in input are integers.

1 \leq N, M \leq 2 \times 10^5

0 \leq K \leq N - 1

Input

Input is given from Standard Input in the following format:

N M K

Output

Print the answer.

Sample Input 1

3 2 1

Sample Output 1

6

The following ways to paint the blocks satisfy the conditions: 112, 121, 122, 211, 212, and 221. Here, digits represent the colors of the blocks.

Sample Input 2

100 100 0

Sample Output 2

73074801

Sample Input 3

60522 114575 7559

Sample Output 3

479519525



Sample input:
3 2 1


Sample output:
6

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(1,0),(-1,0),(0,1),(0,-1)];EightNb=[(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('EWNS',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

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

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1

        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][r-(1<<N)])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][r-(1<<N)]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][r-(1<<N)]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])

    def print(self):
        for i in self.table:
            print(*i)

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True
ans=0

mo=998244353

n,m,k=LI()
cm=Comb(n+100,mo)


ans=0
N=n-1

for i in range(0,k+1):
    #t=pow(m-1,n-1-i,mo)*cm.comb(n-1,i)
    t=pow(m-1,n-1-i,mo)*cm.comb(n-1,i)*m
    ans+=t
    #print(t,end=' ')
print(ans%mo)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

P = 998244353


def make_fac_tables_mod_p(n, p):
    fac = [0] * (n + 1)
    fac_inv = [0] * (n + 1)
    mod_inv = [0] * (n + 1)
    fac[0] = fac[1] = 1
    fac_inv[0] = fac_inv[1] = 1
    mod_inv[1] = 1
    for i in range(2, n + 1):
        fac[i] = (fac[i - 1] * i) % p
        mod_inv[i] = p - mod_inv[p % i] * (p // i) % p
        fac_inv[i] = fac_inv[i - 1] * mod_inv[i] % p
    return fac, fac_inv


def nCk_mod_p(fac, fac_inv, n, k, p):
    return ((fac[n] * fac_inv[n - k]) % p) * fac_inv[k] % p


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

    fac, fac_inv = make_fac_tables_mod_p(N, P)

    ans = M * pow(M - 1, N - 1, mod=P) % P  # k = 0
    for k in range(1, K + 1):
        num = M * pow(M - 1, N - 1 - k, mod=P) % P
        num = num * nCk_mod_p(fac, fac_inv, N - 1, k, P) % P
        ans = (ans + num) % P

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 998244353


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

    def __init__(self, n_max, mod=10 ** 9 + 7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        if n < r:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n + 1):
            fac.append(fac[i - 1] * i % self.mod)
            facinv.append(facinv[i - 1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n + 1)
        modinv[1] = 1
        for i in range(2, n + 1):
            modinv[i] = self.mod - self.mod // i * modinv[self.mod % i] % self.mod
        return modinv


def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


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


def main():
    N, M, K = map(int, input().split())
    comb = Combination(n_max=N, mod=MOD)
    ans = 0

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
sys.setrecursionlimit(1000000)
N,M,K=map(int,input().split())
MOD=998244353

MAX_N=N+10

#a**n mod p を再帰的に求める
def modPow(a,n,p):
    if n==0:
        return 1
    if n == 1:
        #n=1ならaを返す
        return a % p

    elif n % 2 == 1:
        #nが奇数ならば a * modPow(a,n-1(偶数),p)を返す
        return a * modPow(a,n-1,p) % p

    else:
        #nが偶数なら modPow(a,n//2,p) * modPow(a,n//2,p)とすると速い
        t = modPow(a,n//2,p)
        return t * t % p

fac=[None for i in range(MAX_N)]
finv=[None for i in range(MAX_N)]
inv=[None for i in range(MAX_N)]

def COMinit(num):
    global fac
    global finv
    global inv
    fac[0]=1
    fac[1]=1
    finv[0]=1
    finv[1]=1
    inv[1]=1

    for i in range(2,num):
        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
    elif n<0 or k<0:
        return 0
    else:
        return int(fac[n] * (finv[k] * finv[n - k] % MOD) % MOD)


COMinit(MAX_N)

ans=0

for i in range(K+1):
    v=COM(N-1,N-1-K+i)%MOD
    v*=M
    v=v%MOD
    v*=modPow(M-1,N-1-K+i,MOD)
    v=v%MOD
    ans+=v
    ans=ans%MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

def table(n:int, p=998244353):
    global fact, factinv, inv
    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)

def cmb(n:int, r:int, p=998244353):
    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 = mi()
#inf = 998244353
table(2*10**5 + 1)
ans = 0
for i in range(K+1):
    #print(i, ans)
    ans = (ans + cmb(N-1, i) * M * pow(M-1, N-i-1, 998244353)) %998244353

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

p = 998244353


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


def pow_k(x, n, p):
    if n == 0:
        return 1

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

    return K * x % p


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)


ans = 0
for i in range(K + 1):
    po = pow_k(M-1, N-i-1, p)
    tmp = po * M % p
    tmp = tmp * cmb(N-1, i, p) % p
    ans = (ans + tmp) % p

print(ans)

Submission status: Accepted

Solution code:
import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, permutations, product
from typing import List, Dict

# import numpy as np

sys.setrecursionlimit(10**6 + 1)
input = sys.stdin.readline
write = sys.stdout.write


def read_item(cls=int):
    return cls(input())


def read_n_item(cls=int) -> list:
    return [cls(s) for s in input().split()]


def list2d(row, col, init_val=0) -> List[list]:
    return [[init_val] * col for _ in range(row)]


def nCr_factory(limit, mod):
    """ return a combinatorial number operator with upper bound """

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

    ifact = [1] * (limit + 1)
    ifact[-1] = pow(fact[-1], mod-2, mod)

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

    def calc(n, i):
        """ combinatorial number with modulo """
        if i < 0 or i > n:
            return 0
        return fact[n] * ifact[i] % mod * ifact[n-i] % mod
    return calc


# MOD = 10**9 + 7
MOD = 998244353

nCr = nCr_factory(2*10**5, MOD)

N, M, K = read_n_item()
dp = [0] * (N+1)
dp[0], dp[1] = 1, M

for i in range(2, N+1):
    dp[i] = dp[i-1] * (M-1) % MOD

ans = 0
for i in range(K+1):
    remain = N - i
    ans += dp[remain] * nCr(N-1, i)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
mod = 998244353

# mod mでの二項係数を求める
class BiCoeff(object):
    def __init__(self, MAX, m):
        super(BiCoeff, self).__init__()
        fac = [0]*MAX
        finv = [0]*MAX
        inv = [0]*MAX

        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)%m
            inv[i] = m - (inv[m%i] * (m//i))%m
            finv[i] = (finv[i-1] * inv[i])%m

        self.MAX = MAX
        self.m = m
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def calc(self,n,k):
        if n<k:
            return 0
        if n<0 or k<0:
            return 0
        return (self.fac[n] * (self.finv[k]*self.finv[n-k])%self.m)%self.m

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

bicoeff = BiCoeff(10**6, mod)

res = 0
for ki in range(k+1):
    r = bicoeff.calc(n-1, ki)
    if ki==0:
        r = 1
    x = n - ki
    # print(ki, r, x, m * pow(m-1, x-1, mod))
    res += r * m * pow(m-1, x-1, mod)
    res %= mod
print(res)

Submission status: Accepted

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

mm1 = []# m minus 1
div = [0]
conv = [1]
p = 1
d = 1
for i in range(n):
  mm1.append(p)
  p = (p*(m-1))%mod
  div.append(pow(i+1,mod-2, mod))
  conv.append((conv[-1] * (n-i-1) * div[-1])%mod)
  
ans = 0
for i in range(k+1):
  a = m * mm1[n-i-1] * conv[i]
  ans += a%mod
  ans %= mod
print(ans)

Submission status: Accepted

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

mod = 998244353

fac = [1, 1]
ifac = [1, 1]
inverse = [0, 1]

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

ans = 0
for i in range(n-k-1, n):
    j = min(i, n-i-1)
    com = fac[n-1] * ifac[j] * ifac[n-j-1] % mod
    res = m
    e = m - 1
    while i > 0:
        if i & 1:
            res = res * e % mod
        e = e * e % mod
        i >>= 1
    res = res * com % mod
    ans = (ans + res) % mod

print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left

import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 998244353

def main():
    n,m,kk = getList()

    k = m - 1
    ans = 0
    nck = 1
    rui = m
    for itr in range(1, n+1):
        if n - itr <= kk:
            # print(nck, rui)
            ans += (rui*nck) % MOD
            ans %= MOD
            # print(nck, n, itr)
        nck *= (n - itr)
        nck *= pow(itr, MOD-2, MOD)
        nck %= MOD
        rui *= k
        rui %= MOD
        # print(nck, rui)
    print(ans)


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

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

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 )

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

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa
from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


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


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

    MOD = 998244353

    fact = [1, 1]  # fact[n] = (n! mod MOD)
    factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod MOD)
    inv = [0, 1]

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

    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

    E = [1]
    for _ in range(N):
        e = E[-1] * (M - 1)
        e %= MOD
        E.append(e)

    res = 0
    for k in range(0, K + 1):
        a = N - 1 - k

        b = cmb(N - 1, a, MOD) % MOD
        b *= M
        b %= MOD
        b *= E[a]
        b %= MOD

        res += b
        res %= MOD

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

P = mod
inv_t = [0]+[1]
# for i in range(2, M+1):
#     inv_t += [inv_t[P % i] * (P - int(P / i)) % P]


t = [0]*N
t[0] = M
for i in range(1, N):
    t[i] = t[i-1]*(M-1) % mod
# for i in range(K+1):
#     if i == 0:
#         ans += tmp
#     else:

#         tmp *= M-1-i
#         tmp *= inv_t[i]
#         tmp *= inv_t[M-1]
#         tmp %= mod
#         ans += tmp
#         ans %= mod
# print(ans)
MAX_N = N

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1) % mod)

fact_inv[-1] = pow(fact[-1], mod-2, mod)
for i in range(MAX_N+2, -1, -1):
    fact_inv[i] = fact_inv[i+1]*(i+1) % mod


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


for i in range(K+1):
    ans += mod_comb_k(N-1, i, mod) * t[-1-i]


print(ans % mod)

Submission status: Accepted

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

mod = 998244353

def inved(a):
    x, y, u, v, k, l = 1, 0, 0, 1, a, mod
    while l != 0:
        x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
        k, l = l, k % l
    return x % mod
fact = [1 for _ in range(N+M+1)]
invf = [1 for _ in range(N+M+1)]
for i in range(N+M):
    fact[i+1] = (fact[i] * (i+1)) % mod
invf[-1] = inved(fact[-1])
for i in range(N+M, 0, -1):
    invf[i-1] = (invf[i] * i) % mod
MM = [1 for _ in range(N+1)]
for i in range(1, N+1):
    MM[i] = ((MM[i-1] * (M - 1)) % mod)
S = (MM[N-1] * M) % mod
for i in range(K):
    S += (((fact[N-1] * invf[i+1] * invf[N-i-2]) % mod) * (M * MM[N-i-2])) % mod
    S %= mod
print(S)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
mod = 998244353
fac = [1 for _ in range(n+1)]
fac_inv = [1 for _ in range(n+1)]
memo = [1 for _ in range(n+1)]
for i in range(n):
    fac[i+1] = (fac[i] * (i+1)) % mod
    fac_inv[i+1] = pow(fac[i+1], mod-2, mod)
    memo[i+1] = memo[i] * (m-1) % mod

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

print(ans)

Submission status: Accepted

Solution code:
def Pow(a, n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod
mod = 998244353
N, M, K = map(int, input().split())
x = [1]*N
for i in range(1,N):
    x[i] = Pow(i, mod-2)
cmb = [1]*N
for i in range(N-2):
    cmb[i+1] = ((cmb[i]*(N-1-i))%mod*x[i+1])%mod
ans = 0
for i in range(K+1):
    num = Pow(M-1, N-1-i)
    ans = (ans+M*num%mod*cmb[i]%mod)%mod
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
MOD=998244353
list_size = 200001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

def ma():
    return map(int,input().split())
def main():
    n,m,k=ma()
    
    ans=0
    for j in range(k+1):
        ans+=m*comb(n-1,j)%MOD *pow(m-1,(n-1-j),MOD)
        ans%=MOD
    print(ans)

main()

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
mod = 998244353
def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fact[n] * factinv[r] * factinv[n-r] % p
p = 998244353
N = 2*10 ** 5 
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)
s = m
x = m
for i in range(k):
  s = (m*s)%p
for i in range(n-k-1):
  y = x*cmb(k+i,i,p)
  s = (m*s-y)%p
  x = (x*(m-1))%p
print(s)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 998244353
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right


def combination_mod(n, r, mod=MOD):
    # mod取りながらcombination
    if r > n:
        return 0  # このような通りの数は無いため便宜上こう定義する
    r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
    return nf * pow(rf, mod - 2, mod) % mod


def ret_list_comb_r(n, r, mod=MOD):
    '''nC[0:r+1]を返す。for とかで再計算せずに済むように'''
    ret = [1]
    if r > n:
        raise ValueError('rがnより大きいけど大丈夫か？(0通り？)')
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
        ret.append(nf * pow(rf, mod - 2, mod) % mod)
    return ret


N, M, K = read_ints()
N_1C = ret_list_comb_r(N - 1, K)


def ret_ans_when_k(k):
    ret = M
    ret *= pow(M - 1, N - k - 1, MOD)
    ret %= MOD
    ret *= N_1C[k]  # ここの計算量が大きい

    return ret % MOD


ans = 0
for i in range(0, K + 1):
    ans += ret_ans_when_k(i)
    ans %= MOD
print(ans)

Submission status: Accepted

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

def nck(n, k):
    numer, denom = 1, 1
    for i in range(k):
        numer *= n - i
        denom *= k - i
    return numer * pow(denom, MOD-2, MOD) % MOD

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

print(ans)

Submission status: Accepted

Solution code:

MOD = 998244353
MAX = 2*10**5+1
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX
fac[0] = fac[1] = 1
finv[0] = 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 C(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


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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n, m, k = LI()


fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod

inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


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

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

print(ret % mod)

Submission status: Accepted

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

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

ans = pattern[N]
for k in range(1,K+1):
    bunbo = factorial[N-1-k]*factorial[k]
    bunbo %= mod
    bunshi = pattern[N-k]*factorial[N-1]
    bunshi %= mod
    ans += (bunshi*pow(bunbo,mod-2,mod))%mod
    ans %= mod
print(ans)

Submission status: Accepted

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

U=2*10**5
mod=998244353

fact=[1]*(U+1)
fact_inv=[1]*(U+1)

for i in range(1,U+1):
    fact[i]=(fact[i-1]*i)%mod
fact_inv[U]=pow(fact[U],mod-2,mod)

for i in range(U,0,-1):
	fact_inv[i-1]=(fact_inv[i]*i)%mod

def comb(n,k):
    if k<0 or k>n:
        return 0
    x=fact[n]
    x*=fact_inv[k]
    x%=mod
    x*=fact_inv[n-k]
    x%=mod
    return x

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

Submission status: Accepted

Solution code:

def power_func(a,b,p):
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p


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

mod = 998244353
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

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 )

s = 0

for x in range(k+1):
    s += (m * power_func(m-1,n-1-x,998244353) * cmb(n-1,x,998244353)) % 998244353
    s %= 998244353
print(s)