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: Time Limit Exceeded

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  # 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)

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

Submission status: Time Limit Exceeded

Solution code:
#TLE
from collections import defaultdict as dd
n, m, k = map(int, input().split())
mod = 998244353
colors = list(range(1, m+1))

#dp[ブロックn個め][color_now][連続ペア数] = pattern (int)
dp = dd(lambda: dd(lambda: dd(lambda: 0)))
for color in colors:
    dp[1][color][0] = 1

def move_next_block(block_num_now):
    for color_now in colors:
        for next_color in colors:
            #隣を同色に塗る
            if color_now == next_color:
                for renzokupair, pattern in dp[block_num_now][color_now].items():
                    if renzokupair + 1 <= k:
                        dp[block_num_now + 1][next_color][renzokupair + 1] += pattern
                        dp[block_num_now + 1][next_color][renzokupair + 1] %= mod

            #隣を別色に塗る
            else:
                for renzokupair, pattern in dp[block_num_now][color_now].items():
                    dp[block_num_now + 1][next_color][renzokupair] += pattern
                    dp[block_num_now + 1][next_color][renzokupair] %= mod

for i in range(1, n):
    move_next_block(i)

total = 0
for color in colors:
    total += sum(dp[n][color].values())

print(total % mod)

Submission status: Time Limit Exceeded

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

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

result = 0
mod = 998244353

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

print(result)

Submission status: Time Limit Exceeded

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
  key = 1
  for i in range(len(ans)):
    t_ans += (ans[-1-i]*key) % MOD
    t_ans %= MOD
    key *= (N-i-1)
    key //= (i+1)
  print(t_ans)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
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 % MOD)
    cur *= (N-1-k)
    if k==K:break
    cur //= (k+1)    

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: Time Limit Exceeded

Solution code:
def sq(a, b, mod):  # aのb乗を剰余,kは初期値#20191116-D-Knight
    if b == 0:
        return 1
    elif b % 2 == 0:
        return sq(a, b // 2, mod)**2 % mod
    else:
        return sq(a, b - 1, mod) * a % mod


def nCk(n, k, mod=998244353):
    x = max(k, n - k)
    y = min(k, n - k)
    kkai = 1
    for i in range(2, y + 1):
        kkai = (kkai * i) % mod
    nkkai = 1
    for i in range(x + 1, n + 1):
        nkkai = (nkkai * i) % mod
    answer = sq(kkai, mod - 2, mod) * nkkai % mod
    return answer


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

Solution code:
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 % MOD)
    cur *= (N-1-k)
    if k==K:break
    cur //= (k+1)    

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

print((M*ans)%MOD)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def mul(a, b):
    global mod
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    global mod
    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

def div(a, b):
    
    global mod
    return mul(a, power(b, mod-2))

mod=998244353

#print(div(6, 3)) # => 2
#print(div(6,1))
#print(div(10, 2)) # => 5
#print div(3000000000, 2) # => 499999993
#print div(45000000000, 5) # => 999999944
#print div(4000000000, 2000000000) # => 2
#print div(45000000000, 5000000000) # => 9



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

kaijo=[1]
wari=[1]
now=1
for i in range(1,n):
    now*=i
    now%=mod
    kaijo.append(now)
    wari.append(div(1,now))

#print(wari)
ruijo=[1]
now=1

for i in range(n):
    now*=(m-1)
    now%=mod
    ruijo.append(now)

ans=[]

for i in range(n):
    #temp=div(kaijo[n-1],kaijo[i])
    #temp=div(temp,kaijo[n-i-1])
    temp=kaijo[n-1]*wari[i]*wari[n-i-1]
    temp%=mod
    ans.append((temp*ruijo[n-i-1]*m)%mod)

kotae=0

for i in range(k+1):
    kotae+=ans[i]
    kotae%=mod
print(kotae)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import math


def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

    def hoge(k):
        return comb(N - 1, k) * M * ((M - 1) ** (N - k - 1))

    ans = sum([hoge(k) for k in range(K + 1)])

    print(ans % const)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m,k = input().split()
n = int(n)
m = int(m)
k = int(k)
realAns = 0
ans = 1
u = n-1
b = 1
for i in range (k):
  realAns += ans * m * pow(m-1,n-i-1, 998244353)
  ans *= u
  ans = ans//b
  u = u-1
  b = b +1
realAns += ans * m * pow(m-1, n-k-1, 998244353)
print(realAns % 998244353)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
def main():
  N, M, K = map(int, input().split())
  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
  key = 1
  for i in range(len(ans)):
    t_ans += (ans[-1-i]*key) % MOD
    t_ans %= MOD
    key *= (N-i-1)
    key //= (i+1)
  print(t_ans)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m, k = map(int, input().split())
    dp = [0] * (k + 1)

    dp[0] = m

    for i in range(1, n):
        tmp_dp = [0] * (k + 1)
        for j in range(k + 1):
            tmp_dp[j] = (m - 1) * dp[j]
            if j > 0:
                tmp_dp[j] += dp[j - 1]
            tmp_dp[j] %= 998244353
        dp = tmp_dp

    ans = 0
    for i in range(k + 1):
        ans += dp[i]
    print(ans % 998244353)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

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

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

    ret = 0
    comb = 1
    x = m * ((m-1) ** (n-k-1))
    comb_list = [0] * (k+1)
    x_list = [0] * (k+1)
    comb_list[0] = comb
    x_list[0] = x
    for i in range(1, k+1):
        comb = comb * (n-i) // i
        x = x * (m-1) % div
        comb_list[i] = comb
        x_list[i] = x

    for i in range(k+1):
        ret += comb_list[i] * x_list[k-i] % div
        ret %= div

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353

def solve():
    m1pows = [1 for i in range(K + 1)]
    m1pows[0] = M * pow(M - 1, N - 1 - K, MOD) % MOD
    for i in range(1, K + 1):
        m1pows[i] = m1pows[i - 1] * (M - 1) % MOD
    cs = 1
    ans = 0
    for i in range(K + 1):
        ans += cs * m1pows[K - i]
        ans %= MOD
        cs *= (N - 1 - i) % MOD * pow(i + 1, MOD - 2, MOD) % MOD
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int,input().split(" "))
DP = [0 for _ in range(K + 1)]
DP[0] = M
expm_1 = [0 for _ in range(N + 1)]
expm_1[0] = 1
ncr = [0 for _ in range(N + 1)]
ncr[0] = 1
ans = 0

for i in range(N):
    expm_1[i + 1] = (expm_1[i] * (M - 1)) % 998244353
for i in range(N - 1):
    ncr[i + 1] = ncr[i] * (N - i - 1) // (i + 1)
for i in range(K + 1):
    ans += M * expm_1[N - 1 - i] * ncr[i]
    ans %= 998244353
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
mod=998244353
if m==1:print(0 if k!=n-1 else 1);exit()
fact=[1]*(n-1+1)
inv=[1]*(n-1+1)
for i in range(2,n-1+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n-1,1,-1):
    inv[i-1]=inv[i]*i%mod
ans=0
po=pow(m-1,n-1,mod)*m%mod
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)%mod
for i in range(k+1):
    ans+=ue*inv[n-1-i]%mod*inv[i]%mod*po%mod
    po*=iii
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#------------------------------warmup----------------------------
import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
#-------------------game starts now-----------------------------------------------------
n,m,k=map(int,input().split())
a=[0]*(k+1)
a[0]=1
for i in range(1,k+1):
    a[i]=(a[i-1]*(n-i))//(i)
e=[0]*(k+1)
mod=998244353
e[0]=pow(m-1,n-1-k,mod)
for i in range(1,k+1):
    e[i]=((e[i-1])%mod*((m-1)%mod))%mod
ans=0
for i in range(k+1):
    ans+=((e[-1-i])*(a[i]%mod))%mod
    ans%=mod
m=m%mod
print((ans*m)%mod)

Submission status: Time Limit Exceeded

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

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

    ret = 0
    comb = 1
    x = m * ((m-1) ** (n-k-1))
    comb_list = [comb]
    x_list = [x]
    for i in range(1, k+1):
        comb = comb * (n-i) // i
        x = x * (m-1) % div
        comb_list.append(comb)
        x_list.append(x)

    x_list.reverse()
    for i in range(k+1):
        ret += comb_list[i] * x_list[i] % div
        ret %= div

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,m,k=n1()

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
#mod = 10**9 + 7
mod = 998244353

N, M, K = rl()

def combmod(n, k):
	p, q = 1, 1
	for i in range(1, k+1):
		p = p * (n-i+1) % mod
		q = q * i % mod
	return p * pow(q, mod-2, mod) % mod

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# E - Colorful Blocks

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

def comb_mod(n, r, p):
    num = 1
    den = 1
    r = min(r, n-r)
    for i in range(r):
        num = (num * (n-i)) % p
        den = (den * (i+1)) % p
    return num * pow(den, p-2, p)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
n,m,k=mii()


def nCk(n, k, mod=998244353):
    if n < k:
        return 0
    k = min(k, n - k)
    numer = 1
    for x in range(n - k + 1, n + 1):
        numer = (numer * x) % mod
    denom = 1
    for x in range(1, k + 1):
        denom = (denom * x) % mod
    return numer * pow(denom, mod - 2, mod) % mod
 

ans=0

for i in range(k+1):
    temp=1
    temp*=m*((m-1)**(n-1-i))*nCk(n-1,n-1-i)
    ans+=temp%998244353
print(ans%998244353)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,M,K = map(int,input().split())
    MOD = 998244353
    
    if M == 1:
        if K == N-1:
            print(1)
        else:
            print(0)
        exit()
    
    fac = [0]*(N+1)
    fac[0],fac[1] = 1,1
    
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x]*pow(fac[y],MOD-2,MOD)*pow(fac[x-y],MOD-2,MOD))%MOD
    
    ans = 0
    base = pow(M-1,N-K-1,MOD)
    for i in reversed(range(K+1)):
        ret = comb(N-1,i)*(M*base)
        ans += ret
        ans %= MOD
        base *= (M-1)
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
n,m,k=mii()


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

ans=0

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


def power(n, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 1:
        return (n * power(n, k - 1, mod)) % mod
    else:
        return power((n ** 2) % mod, k // 2, mod)


lp = [1]  # (m - 1) ** i
p = 1
for i in range(n - 1):
    p = (p * (m - 1)) % MOD
    lp.append(p)


lf = [1]  # i!
f = 1
for i in range(n - 1):
    f = (f * (i + 1)) % MOD
    lf.append(f)

fn = lf[-1]

answer = 0

for i, f, fr, p in zip(range(k + 1), lf, reversed(lf), reversed(lp)):
    # d = (lf[i] * lf[n - 1 - i]) % MOD
    d = (f * fr) % MOD
    dinv = power(d, MOD - 2, MOD)
    c = (fn * dinv) % MOD
    # n_pattern = (c * m * lp[n - 1 - i]) % MOD
    n_pattern = (c * m * p) % MOD

    answer = (answer + n_pattern) % MOD


print(answer)

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int,input().split())
Q = [[0 for i in range(K+1)] for j in range(N)]
Q[0][0] = M
for i in range(1,N):
    for j in range(K+1):
        if j != 0:
            Q[i][j] = Q[i-1][j-1]+(M-1)*Q[i-1][j]
        else:
            Q[i][j] = (M-1)*Q[i-1][j]
print(sum(Q[N-1])%998244353)

Submission status: Time Limit Exceeded

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

dp = {}
mod = 998244353

for k in range(K+1):
    dp[(1,k)] = M

for i in range(2,N+1):
    for k in range(K+1):
        if k == 0:
            dp[(i, 0)] = dp[(i-1,0)]*(M-1)%mod
        else:
            dp[(i,k)] = dp[(i-1,k)]*(M-1)%mod + dp[(i-1,k-1)]%mod
            dp[(i,k)] %= mod

ans = 0
for k in range(1, K+1):
    ans += dp[(N,k)] % mod
    ans %= mod

print(dp[N,K])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


class ModInt(int):
    
    MOD = 998244353

    def __new__(cls, x, *args, **kwargs):
        return super().__new__(cls, x % ModInt.MOD)

    def __add__(self, other):
        return ModInt(super().__add__(other) % ModInt.MOD)

    def __radd__(self, other):
        return ModInt(super().__radd__(other) % ModInt.MOD)

    def __mul__(self, other):
        return ModInt(super().__mul__(other) % ModInt.MOD)

    def __rmul__(self, other):
        return ModInt(super().__rmul__(other) % ModInt.MOD)

    def __pow__(self, other, *args):
        return ModInt(super().__pow__(other, ModInt.MOD))

    def __rpow__(self, other, *args):
        raise NotImplementedError()

    def __truediv__(self, other):
        inv = ModInt(other).inverse()
        return ModInt(super().__mul__(inv) % ModInt.MOD)

    def __floordiv__(self, other):
        return self.__truediv__(other)

    def __rtruediv__(self, other):
        return ModInt(self.inverse().__mul__(other))

    def __rfloordiv__(self, other):
        return self.__rtruediv__(other)

    def _extgcd(self, a, b):
        assert not isinstance(a, ModInt) and not isinstance(b, ModInt)
        if a < b:
            m, y, x = self._extgcd(b, a)
            return (m, x, y)
        if b == 0:
            x = 1
            y = 0
            return (a, x, y)
        m, y, x = self._extgcd(b, a % b)
        y = y - a // b * x
        return (m, x, y)

    def inverse(self):
        a = int(self)
        m = int(ModInt.MOD)
        n, x, y = self._extgcd(a, m)
        if n != 1:
            raise ValueError("{} and {} are not mutually prime.".format(a, m))
        return ModInt(x)


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


# 998244353は素数
def solve(N, M, K, MOD=998244353):
    # dp[n、k] = nブロック、組k以下での彩色パターン数
    dp = [[ModInt(0) for j in range(K+1)] for i in range(2)]
    dp[0][K] = ModInt(1)
    for i in range(N):
        j0 = i % 2
        j1 = (i+1) % 2
        for k in range(K, max(K-i, -1), -1):
            dp[j1][k] = ModInt(0)
        for k in range(K, -1, -1):
            if i == 0:
                dp[j1][k] += M * dp[j0][k]
            else:
                if k > 0:
                    dp[j1][k-1] += 1 * dp[j0][k]
                dp[j1][k] += (M-1) * dp[j0][k]
    ans = ModInt(0)
    for k in range(K+1):
        ans += dp[N % 2][k]
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
N,M,K = map(int,input().split())
ans = 0
def color(n,m):
    return m*(pow_k(m-1, n-1))

def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x
            x = x ** 2
            x %= mod
            n = (n - 1) // 2
        else:
            x = x ** 2
            x %= mod
            n = n // 2

    return (K * x)%mod
invs = [0] * (N + 1)
invs[1] = 1
for i in range(2, N + 1):
    invs[i] = mod - invs[mod % i] * (mod//i) % mod

def mod_inv_factorial2(n1, n2, m):
    n = max(n1, n2)
    r1 = r2 = 1
    for i in range(1, n+1):
        r1 *= invs[i]
        r1 %= m
        if i == min(n1, n2):
            r2 = r1
    return r1, r2

def mod_factorial(n, m):
    r = 1
    for i in range(1, n+1):
        r *= i
        r %= m
    return r

upper = mod_factorial(N-1,mod)

for i in range(K+1):
    tmp = color(N-i,M)
    lower1,lower2 = mod_inv_factorial2(i,N-1-i,mod)
    ansk = (upper*lower1*lower2*tmp)%mod
    ans += ansk
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

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

def nCr(n, r):
    fac = 1
    finv = 1
    for i in range(r):
        fac *= n-i
        fac %= MOD
        finv *= i+1
        finv %= MOD
    return fac * pow(finv, MOD-2, MOD) % MOD

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

Submission status: Time Limit Exceeded

Solution code:
import sys


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


MOD = 998244353



def power(a, n):
    x = 1
    while n:
        if n & 1:
            x = x * a % MOD
        n >>= 1
        a = a * a % MOD
    return x


def main():
    N, M, K = map(int, input().split())
    answer = M * power(M - 1, N - 1)
    nowu = N - 1
    nowd = 1
    now = 1
    for i in range(K):
        now = now * (nowu) // (nowd)
        ans = M * power(M - 1, N - 1 - i - 1) * now
        nowu -= 1
        nowd += 1
        answer += ans
        answer %= MOD
    print(answer % MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def inv(a, mod):
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a//b
        d = a; a = b; b = d % b
        d = p; p = q; q = d-c*q
    return p+mod if p < 0 else p

def comb(n, r, mod):
    if n < 0 or r < 0 or r > n: return 0
    nu = 1
    de = 1
    for i in range(r):
        nu = nu * (n-i) % mod
        de = de * (i+1) % mod
    return nu * inv(de, mod) % mod


lim=998244353
n,m,k=map(int,input().split())
def f(n,k):
    ans = m %lim
    ans = (ans *pow(m-1,n-k-1,lim)) % lim
    ans = (ans * comb(n-1,k,lim)) % lim
    return ans

#n,m,k = 60522, 114575, 7559
sum_ = 0
for j in range(k+1):
    ans = m %lim
    #print(m-j-1,n,j)
    ans = (ans *pow(m-1,n-j-1,lim)) % lim
    ans = (ans * comb(n-1,j,lim)) % lim
    #print(ans)
    sum_ = (sum_+ans) % lim
print(sum_)

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353
# Combination under a prime modulo: nCk % p
def combmod(n, k, p):
    if k > n:
        return 0
    if k > n - k:
        k = n - k
    num, den = 1, 1
    for i in range(k):
        num = num * (n - i) % p
        den = den * (i + 1) % p
    # By Fermat's little theorem,
    # a^(p-1) ≡ 1 mod p
    # i.e. a^(p-2) ≡ a^(-1) mod p
    inv_dev = pow(den, p - 2, p)
    return num * inv_dev % p


def solve():
    ans = 0
    for i in range(K + 1):
        ans += (combmod(N - 1, i, MOD) * M) % MOD * pow(M - 1, N - 1 - i, MOD)
        ans %= MOD
    return ans


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

Submission status: Time Limit Exceeded

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


def power(n, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 1:
        return (n * power(n, k - 1, mod)) % mod
    else:
        return power((n ** 2) % mod, k // 2, mod)


lp = [1]  # (m - 1) ** i
p = 1
for i in range(n - 1):
    p = (p * (m - 1)) % MOD
    lp.append(p)


lf = [1]  # i!
f = 1
for i in range(n - 1):
    f = (f * (i + 1)) % MOD
    lf.append(f)

fn = lf[-1]

answer = 0

fr = 1
for i in range(n - 1 - (k + 1)):
    fr = (fr * (i + 1)) % MOD


f = 1
for i, f, fr, p in zip(range(k + 1), lf, reversed(lf), reversed(lp)):
    # d = (lf[i] * lf[n - 1 - i]) % MOD
    d = (f * fr) % MOD
    dinv = power(d, MOD - 2, MOD)
    c = (fn * dinv) % MOD
    # n_pattern = (c * m * lp[n - 1 - i]) % MOD
    n_pattern = (c * m * p) % MOD

    answer = (answer + n_pattern) % MOD


# def n_pattern(n_pair):
#     return (lc[n_pair] * m * power(m - 1, n - 1 - n_pair, MOD)) % MOD


# answer = 0
# for i in range(k + 1):
#     answer = (answer + n_pattern(i)) % MOD


print(answer)