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

class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)
    def __int__(self):
        return self.x

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __mod__(self, other):
        return (
            ModInt(
                other.x
            ) if isinstance(other, ModInt) else
            self.x
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
    
    def __iadd__(self,other):
        self.x += other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self

    def __isub__(self,other):
        self.x += ModInt(MOD - other.x) if isinstance(other, ModInt) else ModInt(MOD - other)
        return self

    def __imul__(self, other):
        self.x *= other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self
    
    def __ifloordiv__(self, other):
        self.x *= pow(int(other), MOD - 2, MOD)
        return self
    
    def factorical(self,n):
        tmp = ModInt(1)
        for i in range(n):
            tmp *= (i+1)
        return tmp
    
    #m:int MOD
    def modinv(self,a,m=MOD):
        b = m
        u = 1
        v = 0
        while(b):
            t = a//b
            a -= t * b
            a,b = b,a
            u -= t * v
            u,v = v,u
        return ModInt(u)

    def comb(self,n,r):
        n = int(n)
        r = int(r)
        if r > n or n < 0 or r < 0:
            return 0
        m = n+1
        nterms = min(r, n-r)
        numerator = ModInt(1)
        denominator = ModInt(1)
        for j in range(1, nterms + 1):
            numerator *= m - j
            denominator *= j
        return numerator * self.modinv(denominator.x)

def COMinit():
    fac[0] = ModInt(1)
    fac[1] = ModInt(1)
    finv[0] = ModInt(1)
    finv[1] = ModInt(1)
    inv[1] = ModInt(1)
    for i in range(2,lim):
        fac[i] = ModInt(fac[i - 1] * i)
        inv[i] = ModInt(MOD - inv[MOD%i] * (MOD // i))
        finv[i] = ModInt(finv[i - 1] * inv[i])

def cmb(n,k) -> ModInt:
    if int(n) < int(k):
        return ModInt(0)
    if int(n) < 0 or int(k) < 0:
        return ModInt(0)
    if fac[0] == 0:
        COMinit()
    tmp = ModInt(finv[int(k)] * finv[int(n - k)])
    tmp *= fac[int(n)]
    return tmp


        
if __name__ == "__main__":
    n,m,k = map(int,input().split())
    n = ModInt(n)
    m = ModInt(m)
    ans = ModInt(0)
    for i in range(k+1):
        ans += cmb(n-1,i) * m * pow(m-1,n-i-1)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
mod= 998244353

def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from itertools import combinations

N,M,K=(int(x) for x in input().rstrip('\n').split())
res = 0
for i in range(K+1):
  add = (M-1)**(N-i-1)
  add = M*add
  pat = len(list(combinations(range(N-1),N-i-1)))
  res += add*pat
print(res%998244353)

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 * pow(M - 1, N - 1 - i, MOD)
        ans %= MOD
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

count = 0
C = 998244353

def m(num_pattern_match, x):
  tmp = 0
  for i in range(len(num_pattern_match)-1,-1,-1):
    tmp += num_pattern_match[i]*x
    if i>0:
      num_pattern_match[i] = tmp%C
      tmp = tmp//C
    else:
      num_pattern_match[i] = tmp
  return num_pattern_match

def q(num_pattern_match, x):
  tmp = 0
  for i in range(len(num_pattern_match)):
    tmp = tmp*C+num_pattern_match[i]
    num_pattern_match[i] = tmp//x
    tmp = tmp%x
  return num_pattern_match

for i in range(K,-1,-1):
  if i==K:
    list_num_pattern_match = [1]
    num_pattern_match = [0,1]
    num_pattern_paint = M
    for j in range(1,K+1):
      num_pattern_match = m(num_pattern_match,N-j)
      num_pattern_match = q(num_pattern_match,j)
      list_num_pattern_match.append(num_pattern_match[-1])
    for j in range(N-1-K):
      num_pattern_paint = (num_pattern_paint*(M-1))%C
  else:
    num_pattern_paint = (num_pattern_paint*(M-1))%C
  count = (count+(list_num_pattern_match[i])*(num_pattern_paint))%C

print(count)

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, -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:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def comb_mod_faster(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k = min(n-k,k)
    ans = 1
    inv = [1]*(k+1)
    if k>=1:
        ans *= (n-k+1)%mod
    for i in range(2,k+1):
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        ans = ans*(n-k+i)*inv[i]%mod
    return ans

def power_func(a,n,p):
    bi = str(format(n,"b"))#2進表現に
    res = 1
    for i in range(len(bi)):
        res = (res*res) % p
        if bi[i]=="1":
            res = (res*a) % p
    return res

n,m,k = myinput()

mod = 998244353

# ans = 100*(99**99) % mod
# print(ans)

# ls = [0]*(k+1)
# for i in range(k+1):
#     ls[i] = comb_mod_faster(n,i,mod)
# print(ls)

# ans = 0
# for i in range(k+1):
#     t = ls[i]
#     ans += ( (m-1)**(n-t) ) * (m**t)
#     ans %= mod 
# print(ans%mod)

ans = 0
for i in range(k+1):
    t = comb_mod_faster(n-1,i,mod)
    # print(i,t)
    ans1 = power_func(m-1,n-1-i,mod)
    # print(ans1)
    # ans2 = power_func(1,i,mod)
    # print(ans2)
    ans += ( m * t * ans1 ) % mod
    # print(ans)
print(ans%mod)

Submission status: Time Limit Exceeded

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

ans = 0
w = 998244353

from scipy.special import comb

for i in range(K+1):
  ans += (M*((M-1)**(N-1-i))*comb(N-1,i,exact=True))%w
print(ans%w)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
def comb(n, k, MOD):
    if n < k or n < 0 or k < 0:
        return 0
    if k == 0:
        return 1
    iinv = [1] * (k + 1)
    ans = n
    for i in range(2, k + 1):
        iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
        ans *= (n + 1 - i) * iinv[i] % MOD
        ans %= MOD
    return ans
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,MOD))%MOD
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce


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:
import sys
sys.setrecursionlimit(100000000)
mod=0
def F(curr,N,M,K):
    global mod
    if curr==N:
        return 1
    if curr==0:
        return (M*F(curr+1,N,M,K))%mod
    else:
        a=0
        if K>0:
            a=F(curr+1,N,M,K-1)%mod
        b=(M-1)*F(curr+1,N,M,K)%mod
        return (a+b)%mod
N,M,K=map(int,input().strip().split())
mod=998244353
print(F(0,N ,M, K)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

MOD = 998244353
n,m,k = MI()

s = [1]
for i in range(2, n):
    s.append(s[-1]*i%MOD)
if m == 1 and k < n-1:
    print(0)
    exit(0)
elif m == 1 and k == n-1:
    print(1)
    exit(0)
ans = m*pow(m-1, n-1, MOD)%MOD
for i in range(1, k+1):
    tmp = m*pow(m-1, n-1-i, MOD)*s[n-2]*pow(s[n-2-i], MOD-2, MOD)*pow(s[i-1], MOD-2, MOD)
    ans += tmp
    ans %= MOD
print(ans)

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=(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
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC167e


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと

    def dump(*args):
        sys.stderr.write(str(args))
    n, m, k = map(int, input().split())
    # dp[i][j][k]=i番目までのブロックを考えるとき、

    MOD = 998244353

    dp = [[0] * (k+1) for _ in range(n+1)]
    dp[1][0] = m
    for i in range(n):
        for j in range(k+1):
            dp[i + 1][j] += dp[i][j] * (m - 1) % MOD
            if j < k:
                dp[i + 1][j + 1] += dp[i][j] % MOD
    print(sum(dp[n]) % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod =998244353
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

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

    #     dp=copy(ndp)
    # ans=(dp[0]+dp[1])%mod
    # #print(ans)

    #n0=math.factorial(N-1)
    #ks=[1]*(N-1+1)
    #for k in range(2,N-1+1):
    #    ks[k]=ks[k-1]*k
    ans=0
    c0=1
    #c1=pow(M-1,N-1,mod)
    c1s=[1]*(N-1+1)
    for i in range(1,N):
        c1s[i]=c1s[i-1]*(M-1)%mod
    
    ans=c1s[N-1]*c0
    for k in range(1,K+1):
        #print((n0//ks[k]//ks[N-1-k]))
        c0=(c0*(N-k)//(k))
        c1=c1s[N-1-k]
        ans+=(c1*c0)%mod
    #print(ks)
    ans=(ans*M)%mod
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    # import numpy as np
    import math
    # import random
    input = stdin.readline

    p = 998244353

    def pow_k(x, n):
        """
        O(log n)
        """
        if n == 0:
            return 1

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

        return (K * x)%p

    n, m, k = map(int, input().split())
    if m == 1:
        if k < n-1:
            print(0)
        else:
            print(1)
        exit()

    ans = 0
    first = pow_k(m-1, n-k-1)
    first_cmb = math.factorial(n-1) // math.factorial(k) // math.factorial(n - k-1)
    for i in range(k, -1, -1):
        ans += (first_cmb*first)%p
        first = (first*(m-1))%p
        first_cmb = (first_cmb*i)//(n-i)
    ans = ans*m
    print(ans%p)

Submission status: Time Limit Exceeded

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

dp = [ [0] * (K+1) for _ in range(N+1)]

# 1個目
dp[1][0] = M

for i in range(1,N):
    for k in range(min(K+1, i+1)):
        dp[i+1][k] += dp[i][k] * (M-1) % MOD  # 違う色
        if K > k:
            dp[i+1][k+1] += dp[i][k] % MOD # 同じ色

print(sum(dp[N]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
n, m, k = map(int, input().split())
ans = 0
for i in range(k + 1):
    ans = (ans + m * pow(m - 1, n - 1 - i, 998244353) * cmb(n-1,i)) % 998244353
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n, m, k = map(int, input().split())
color = [i for i in range(m)]
ans = 0
def dfs(i, daburi, num):
    global ans
    if i == n-1:
        if daburi == k:
            ans += num % 998244353
            return 
        elif daburi < k:
            ans += num % 998244353
            return
    if daburi > k:
        return
    dfs(i+1, daburi, num*(m-1)% 998244353)
    dfs(i+1, daburi+1, num% 998244353)
dfs(0, 0, m)
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)
#print(a)
ans=0
mod=998244353
for i in range(k+1):
    ans+=((m%mod)*pow(m-1,n-i-1,mod)*(a[i]%mod))%mod
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

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

p = 998244353
N = 10 ** 6
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)

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def comb_mod_faster(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k = min(n-k,k)
    ans = 1
    inv = [1]*(k+1)
    if k>=1:
        ans *= (n-k+1)%mod
    for i in range(2,k+1):
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        ans = ans*(n-k+i)*inv[i]%mod
    return ans

def power_func(a,n,p):
    bi = str(format(n,"b"))#2進表現に
    res = 1
    for i in range(len(bi)):
        res = (res*res) % p
        if bi[i]=="1":
            res = (res*a) % p
    return res

n,m,k = myinput()

mod = 998244353

# ans = 100*(99**99) % mod
# print(ans)

# ls = [0]*(k+1)
# for i in range(k+1):
#     ls[i] = comb_mod_faster(n,i,mod)
# print(ls)

# ans = 0
# for i in range(k+1):
#     t = ls[i]
#     ans += ( (m-1)**(n-t) ) * (m**t)
#     ans %= mod 
# print(ans%mod)

ans = 0
for i in range(k+1):
    t = comb_mod_faster(n-1,i,mod)
    # print(i,t)
    ans1 = power_func(m-1,n-1-i,mod)
    # print(ans1)
    ans2 = power_func(1,i,mod)
    # print(ans2)
    ans += ( m * t * ans1 * ans2 ) % mod
    # print(ans)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def e_colorful_blocks(MOD=998244353):
    N, M, K = [int(i) for i in input().split()]
    # dp[i][k]: i 番目まで見たときに、同じ色で塗られている組が k 組である
    dp = [[0] * (K + 1) for _ in range(N)]
    dp[0][0] = M

    for i in range(N - 1):
        for k in range(min(i, K) + 1):
            if k == K:
                dp[i + 1][k] += dp[i][k] * (M - 1)  # 異なる色で塗るしかない
                dp[i + 1][k] %= MOD
            else:
                dp[i + 1][k] += dp[i][k] * (M - 1)  # 左と異なる色で塗る
                dp[i + 1][k + 1] += dp[i][k]  # 左と同じ色で塗る
                dp[i + 1][k] %= MOD
                dp[i + 1][k + 1] %= MOD
    return sum([dp[N - 1][k] for k in range(K + 1)]) % MOD

print(e_colorful_blocks())

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline

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


C = [-1] * (N + 1)


def comb(N, r):
    r = min(r, N - r)

    if C[r] != -1:
        return C[r]
    else:
        ue = 1
        shita = 1

        for i in range(r):
            ue *= (N - i)
            ue %= mod
            shita *= (i + 1)
            shita %= mod

        C[r] = ue * pow(shita, mod - 2, mod)
        C[r] %= mod
        return C[r]


ans = M * pow(M - 1, N - 1 - K, mod) * comb(N - 1, K)
tmp = M * pow(M - 1, N - 1 - K, mod)

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

print(ans % mod)
# print(C)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

N, M, K = map(int, readline().split())
P = 998244353
def mod_prod(a,b):
    return a * b % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n // 2
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret

ans = 0
_n = N - 1
for k in range(K + 1):
    a = N - k
    # N-1 Comb k
    if k == 0:
        comb = 1
    elif k == 1:
        comb = _n
    else:
        comb = comb * mod_div((_n - k + 1), k) % P
    b = M * mod_pow(M-1, a-1) % P
    b = b * comb % P
    ans += b
    ans %= P


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N, M, K = lr()
    MOD = 998244353
    dp = defaultdict(lambda: -1)
    def narabi(n, k):
        tmp = 0
        if k > K:
            return 0
        if n == 0:
            return 1
        if dp[n, k] != -1:
            return dp[n, k]
        if n == N:
            tmp += (M*narabi(n-1, k))%MOD
        else:
            tmp += (narabi(n-1, k+1) + (M-1)*narabi(n-1, k))%MOD
        tmp %= MOD
        dp[n, k] = tmp
        return tmp
    ans = narabi(N, 0)
    print(ans)
resolve()

Submission status: Time Limit Exceeded

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

dp = [ [0] * (K+1) for _ in range(N+1)]

# 1個目
dp[1][0] = M

for i in range(1,N):
    for k in range(K+1):
        dp[i+1][k] += dp[i][k] * (M-1) % MOD  # 違う色
        if K > k:
            dp[i+1][k+1] += dp[i][k] % MOD # 同じ色


print(sum(dp[N]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():

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

    dp=[[0]*(K+1) for _ in range(N)]#Kは０組の場合もあるのでK＋1

    MOD=998244353

    def pow_mod(n,k,m):#nのk乗をmod mしたものを算出する関数
        if k==0:
            return 1
        if k%2==0:
            return (pow_mod(n,k//2,m)**2)%m
        if k%2==1:
            return (pow_mod(n,k-1,m)*n%m)%m

    dp[0][0]=M%MOD
    for i in range(1,N):
        dp[i][0]=(M%MOD)*pow_mod(M%MOD-1,i,MOD)#((M%MOD-1)**(N))

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

    #print(dp)
    print(sum(dp[N-1][j] for j in range(K+1))%MOD)

main()

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-1,mod)
for i in range(k+1):
    ans=(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)

Submission status: Time Limit Exceeded

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

def comb(n,k,p):
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n, m, k = map(int, input().split())
color = [i for i in range(m)]
ans = 0
def dfs(i, daburi, num):
    global ans
    if i == n-1:
        if daburi == k:
            ans += num % 998244353
            return 
        elif daburi < k:
            ans += num % 998244353
            return
    if daburi > k:
        return
    dfs(i+1, daburi, num*(m-1))
    dfs(i+1, daburi+1, num)
dfs(0, 0, m)
print(ans% 998244353)