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

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)

Submission status: Time Limit Exceeded

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


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 #出力の制限

ans=0
for k in range(K+1):
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル

    for i in range( 2, n ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )
    ans=(ans+m*pow(m-1,n-k-1)*cmb(n-1,k,mod))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

def modPow(a, b, mod):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%mod

        a = (a**2)%mod
        b //= 2

    return x


def getModInv(a):
    return modPow(a, MOD-2, MOD)


def f(N,M,K):
    s = 0
    c = 1
    c1 = N-1
    c2 = 1
    d = modPow(M-1, N, MOD)
    d1 = getModInv(M-1)


    for k in range(K+1):
        d = d*d1%MOD

        s = (s + c*d)%MOD

        c = c*c1%MOD*getModInv(c2)%MOD
        c1 -= 1
        c2 += 1

    return (s*M)%MOD


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

if M == 1 and N == K+1:
    print(1)
else:
    print(f(N,M,K))

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int,input().split())
mod = 998244353
ans = (M**N)%mod
def combination(n,k):
    bunbo,bunsi = 1,1
    for i in range(k):
        bunsi = bunsi*(n-i)%mod
        bunbo = bunbo*(i+1)%mod
    return bunsi*pow(bunbo,mod-2,mod)%mod

for t in range(K+1,N):
    tmp = combination(N-1,t)
    ans = (ans - (tmp*M%mod)*pow(M-1,N-1-t,mod)%mod)%mod
print(ans)

Submission status: Time Limit Exceeded

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

def comb(n, r, mod=MOD):
    r = min(n - r, r)
    res = 1
    fac = 1
    for i in range(r):
        res *= n - i
        res %= mod
        fac *= i + 1
        fac %= mod
    return res * pow(fac, mod-2, mod) % mod

def main():
    N, M, K = map(int, readline().rstrip().split())
    res = 0
    for k in range(K+1):
        n = N - k
        res += comb(N-1, k, MOD) * pow(M-1, n-1, MOD) * M
        res %= MOD
    
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from math import factorial

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


def main():
    N, M, K = map(int, input().split())
    MOD = 998244353
    fac = [0] * (N + 10)
    finv = [0] * (N + 10)
    inv = [0] * (N + 10)
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, N + 2):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

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

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

    print(ans % MOD)

    return


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:
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 = {0: 1}  # (m - 1) ** i
p = 1
for i in range(n - 1):
    p = (p * (m - 1)) % MOD
    lp[i + 1] = p


lf = {0: 1}  # i!
f = 1
for i in range(n):
    f = (f * (i + 1)) % MOD
    lf[i + 1] = f

fn = lf[n - 1]


answer = 0

for i in range(k + 1):
    d = (lf[i] * lf[n - 1 - i]) % MOD
    dinv = power(d, MOD - 2, MOD)
    c = (fn * dinv) % MOD
    n_pattern = (c * m * lp[n - 1 - i]) % 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)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

if n == 1:
    print(m)
    exit()

X = [[0]*(k+2) for _ in range(k+2)]
for i in range(k+2):
    if i == 0:
        continue
    X[i][i-1] = 1
    X[i][i] = m-1

def mul(a, b):
    c = [[0]*len(b[0]) for i in range(len(a))]
    for i in range(len(a)):
        for k in range(len(b)):
            for j in range(len(b[0])):
                c[i][j] = (c[i][j] + a[i][k]*b[k][j])%mod

    return c

#A**n
def pow(a, n):
    b = [[0]*len(a) for i in range(len(a))]
    for i in range(len(a)):
        b[i][i] = 1
    while n > 0:
        if n & 1 == 1:
            b = mul(a, b)
        a = mul(a, a)
        n = n>>1
    return b

#print(X)
Y =  pow(X, n-1)
#Z0 = [0]*(k+2)
#Z[1] = m
ans = 0
#print(Y)
for i in range(k+2):
    ans += Y[i][1]*m
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353

def bi(x):
    o = []
    while x != 0:
        o.append(x%2)
        x //= 2
    return o

def modpow(m,n):
    o = 0
    leo = 0
    if n == 1000000005:
        o = [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1]
        leo = 30
    else:
        o = bi(n)
        leo = len(o)
    p = [m] + [0] * (leo - 1)
    for i in range(1,leo):
        a = p[i-1]
        a *= a
        a %= mod
        p[i] = a
    b = 1
    for i in range(leo):
        if o[i]:
            b *= p[i]
            b %= mod
    return b

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

C = [1]*(K+1)
for i in range(1,K+1):
    C[i] = C[i-1] * (N-i) // i

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

ans = 0
for k in range(0,K+1):
    ans += C[k] * M * M1[N-k-1]
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 998244353
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

fact = [1]
for i in range(1, N+10):
    fact.append(fact[-1] * i % MOD)
def rev(x):
    return pow(x, MOD-2, MOD)
def cmb(i, k):
    if(i < k): return 0
    return fact[i] * rev(fact[k]) * rev(fact[i-k]) % MOD

def count(m, k):
    combo = cmb(N-1, k)
    col = m * pow(m-1, N-k-1, MOD)
    val = (combo*col)%MOD
    return val

cnt = 0
for k in range(0, K+1):
    addval = count(M, k)
    cnt += addval
    cnt %= MOD

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000000)


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

DP = [[-1] * (K+1) for _ in range(N+1)]


def dpdp(n, k):
    if DP[n][k] != -1:
        return DP[n][k]
    if n-1 <= k:
        DP[n][k] = pow(M, n-1, mod)
        return pow(M, n-1, mod)
    if k == 0:
        DP[n][k] = pow(M-1, n-1, mod)
        return pow(M-1, n-1, mod)
    if n == 1:
        DP[n][k] = M % mod
        return M % mod

    return (dpdp(n-1, k-1) % mod + (M-1) * dpdp(n-1, k) % mod) % mod


print(dpdp(N, K) * M % mod)

Submission status: Time Limit Exceeded

Solution code:
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)    
curpower = 1
for n in range(N):#M-1 ** n
   POWER.append(curpower)
   curpower *= M-1
   curpower %= MOD

ans = 0

for k in range(K+1):
    ans += M * POWER[N-1-k] * NcK[k]
    #M-1 ** N-1-k ということは…？
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
n,m,k=map(int,input().split())
w=998244353
t=0
c=1
b=m*((m-1)**(n-1))%w
for i in range(k+1):
    t += c * b
    t %= w
    c*=(n-1-i)
    c*=power_func(i+1,w-2,w)
    c%=w
    b*=power_func(m-1,w-2,w)
    b%=w

print(t)

Submission status: Time Limit Exceeded

Solution code:
#左からn個目でendが特定の色の場合に
N,M,K = list(map(int,input().split()))

def xgcd(a, b):
  x0, y0, x1, y1 = 1, 0, 0, 1
  while b != 0:
    q, a, b = a // b, b, a % b
    x0, x1 = x1, x0 - q * x1
    y0, y1 = y1, y0 - q * y1
  return a, x0, y0
def modinv(a, m):
  g, x, y = xgcd(a, m)
  if g != 1:
    raise Exception('modular inverse does not exist')
  else:
    return x % m
def combination(n, k, mod=1e9+7) -> int:
  ret = 1
  for i in range(1, k+1):
    ret = (ret * (n-k+i) * modinv(i, mod))%mod
  return int(ret)

def pow(base, exponent, mod=1e9+7) -> int:
  if exponent == 0:
    return 1
  if exponent > 1:
    d,m = divmod(exponent, 2)
    return (base**m * pow(base, d, mod)**2 ) % mod
  else:
    return base

m = 998244353
res = 0
B = 1
for k in range(K+1):
  A = M * pow(M-1,N-k-1,m)
  if k>0:
    B = B*(N-k)//k 
  res = (res+ A*B)%m
print (res)

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+=(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%mod)

Submission status: Time Limit Exceeded

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

def mul(a, b):
    return ((a % P) * (b % P)) % P
 
def div(x, y):
    return mul(x, pow(y, P-2, P))
 
def comb(n, r):
    r = min(r, n - r)
    
    x = 1
    for i in range(n, n - r, -1):
        x = (x * i) % P
        
    y = 1
    for i in range(1, r+1):
        y = (y * i) % P
    return div(x, y)

res = 0
for k in range(K + 1):
    m = M * pow(M - 1, N - 1 - k, P)
    c = comb(N - 1, k)
    res += ((m % P) * c) % P
print(res % P)

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(2*(10**5),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
print(ans%mod)

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)
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)
for i in range(k+1):
    ans+=ue*inv[n-1-i]*inv[i]*m*po%mod
    po*=iii
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def mod_fra(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def mod_power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return mod_power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * mod_power(n, r-1, mod) % mod

def mod_comb(n, k, mod):
    a=mod_fra(n, mod)
    b=mod_fra(k, mod)
    c=mod_fra(n-k, mod)
    return (a * mod_power(b, mod-2, mod) * mod_power(c, mod-2, mod)) % mod
def main():
    n,m,k=map(int,input().split())
    mod=998244353
    ans=0
    for kx in range(k+1):
        ans+=mod_comb(n-1,kx,mod)*m*(m-1)**(n-1-kx)%mod
    print(ans%mod)


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

ways = [0] * n

for i in range(0, n):
    if i == 0:
        ways[i] = m
    else:
        way = ways[i - 1] * (m - 1)
        way %= 998244353
        ways[i] = way

total = 0
nCr = 1
for i in range(k + 1):
    n2 = n - 1
    nCr = nCr * (n2 - (i - 1)) // i if i > 0 else 1
    total += ways[- (i + 1)] * nCr
    total %= 998244353

print(total)

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)
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)
for i in range(k+1):
    ans+=ue*inv[n-1-i]*inv[i]*m*po%mod
    po*=iii
print(ans%mod)

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)
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)
for i in range(k+1):
    ans+=ue*inv[n-1-i]*inv[i]%mod*m*po%mod
    po*=iii
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod

def cmb(n, r, MOD):
    if n < r:
        return 0
    if n-r < r:
        r = n-r
    comb = 1
    for x in range(n-r+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, r+1):
        d = (d * x) % MOD
    comb *= powmod(d, MOD-2, MOD)
    return comb % MOD


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

ans = 0

if K == n-1:
    ans = powmod(m, n, mod)
elif K < (n-1)//2:
    for k in range(K+1):
        ans += m * powmod(m-1, n-1-k, mod) * cmb(n-1, k, mod)
        ans %= mod
else:
    ans = powmod(m, n, mod)
    for k in range(K+1, n):
        ans -= m * powmod(m - 1, n - 1 - k, mod) * cmb(n - 1, k, 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]


# lc = []  # n - 1 C i
answer = 0
for i in range(k + 1):
    d = (lf[i] * lf[n - 1 - i]) % MOD
    dinv = power(d, MOD - 2, MOD)
    c = (fn * dinv) % MOD
    # lc.append(c)
    n_pattern = (c * m * lp[n - 1 - i]) % 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)

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 = 0

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

print(ans)
# print(C)

Submission status: Time Limit Exceeded

Solution code:
def main():
  mod=998244353
  n,m,k=map(int,input().split())
  def ncr_mod(n,r,mod):
    a,b=1,1
    for i in range(r):
      a*=n-i
      a%=mod
      b*=i+1
      b%=mod
    return (a*pow(b,mod-2,mod))%mod
  ans=m*pow(m-1,n-1,mod)
  ans%=mod
  for i in range(1,k+1):
    ans+=m*pow(m-1,n-1-i,mod)*ncr_mod(n-1,i,mod)
    ans%=mod
  print(ans)
    
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def com(n,r,mod):
    k=min(r,n-r)
    C=1
    for i in range(1,k+1):
        C=(C*(n+1-i)*pow(i,mod-2,mod))%mod
    return C

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

cnt = 0
for i in range(k + 1):
    cnt = (cnt + com(n - 1, i, mod) * m * pow(m - 1, n - 1 - i, mod))%mod
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map (int,input().split())
def comb(n, r, mod):
  a = 1
  b = 1
  r = min(r, n - r)
  for i in range(r):
    a = a * (n - i) % mod
    b = b * (i + 1) % mod
  return a * pow(b, mod - 2, mod) % mod
mod = 998244353
ans = 0
if k <=  n//2:
    for i in range(k+1):

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

Submission status: Time Limit Exceeded

Solution code:
String = input()
list1 = String.split(" ")
n = int(list1[0])
m = int(list1[1])
k = int(list1[2])
lis = [0]*n
result = 0

while lis[n-1] < m:
    if result >= 998244353:
        break
    judge = 0
    for a in range(n-1):
        if lis[a] == lis[a+1]:
            judge += 1
    if judge <= k:
        result += 1
    if judge > k + 1:
        index = 0
        while index < n - 2:
            if lis[index] == lis[index+1]:
                lis[index] += 1
                break
            index += 1
    lis[0] += 1
    for b in range(n -1):
        if lis[b] == m:
            lis[b] = 0
            lis[b+1] += 1
print(result)

Submission status: Time Limit Exceeded

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

def mul(a, b):
    return ((a % P) * (b % P)) % P
 
def div(x, y):
    return mul(x, pow(y, P-2, P))
 
def comb(n, r):
    x = 1
    for i in range(n, n - r, -1):
        x = (x * i) % P
        
    y = 1
    for i in range(1, r+1):
        y = (y * i) % P
    return div(x, y)

res = 0
for k in range(K + 1):
    m = M * pow(M - 1, N - 1 - k, P)
    c = comb(N - 1, k)
    res += ((m % P) * c) % P
print(res % P)

Submission status: Time Limit Exceeded

Solution code:
def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))

n,m,k = mp()

def combination(n, r, mod):
    np1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (np1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

mod = 998244353
ans = 0
for i in range(k+1):
    ans += combination(n-1, i, mod) * pow(m-1, n-1-i, mod)
    ans %= mod
print((ans*m)%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 = (M - 1) ** (N - k - 1) % mod
    result = (result + c * m * n) % mod

print(result)

Submission status: Time Limit Exceeded

Solution code:
import math


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


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

ways = [0] * n

for i in range(0, n):
    if i == 0:
        ways[i] = m
    else:
        way = ways[i - 1] * (m - 1)
        way %= 998244353
        ways[i] = way

total = 0
for i in range(k + 1):
    mul = comb(n - 1, i) if i > 0 else 1
    total += ways[- (i + 1)] * mul
    total %= 998244353

print(total)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map (int,input().split())
def comb(n, r, mod):
  a = 1
  b = 1
  r = min(r, n - r)
  for i in range(r):
    a = a * (n - i) % mod
    b = b * (i + 1) % mod
  return a * pow(b, mod - 2, mod) % mod
mod = 998244353
ans = 0
if k <=  n//2:
    for i in range(k+1):

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

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())
mod = 998244353
def pascal(n):
    line = [1]
    for k in range(n):
        line.append(int(line[k] * (n-k) // (k+1)) )
    return line
line = pascal(n-1)
#print(line)

mm1 = [1]

for i in range(1, n+1):
    mm1 += [(mm1[-1] * (m-1)) % mod]

mm = [1]
for i in range(1, n+1):
    mm += [(mm[-1] * (m)) % mod]

ans = 0
for i in range(k+1):
    if i == 0:
        ans += (mm1[n-1] * m ) % mod
        continue
    if i == n-1:
        ans += (m)
        break
    ans += (mm1[n-1-i] * line[i] * m) % mod

ans = (ans)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys
import functools
import math

sys.setrecursionlimit(100000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 998244353  # type: int


@functools.lru_cache(maxsize=None)
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def solve(N: int, M: int, K: int):
    if N == 1:
        print(M)
        exit()
    #
    # @functools.lru_cache(maxsize=None)
    # def f(i, k):
    #     if k < 0:
    #         return 0
    #     if i == N - 1:
    #         return M - 1 if k == 0 else M
    #     if i == 0:
    #         return M * f(i + 1, k)
    #     # diff color + same color
    #     return (M - 1) * f(i + 1, k) + f(i + 1, k - 1)
    #
    # print(f(0, K)%MOD)
    n = N - 1
    nCr = 1
    _sum = 0
    # (M - 1) ** (N - k - 1)
    e = [1]
    for i in range(N):
        e.append(e[-1] * (M - 1) % MOD)
    # print('ok')
    for k in range(K + 1):
        # print(nCr)
        _sum += M * e[N - k - 1] * nCr % MOD
        # print(nCr%MOD, comb(N - 1, k)%MOD)
        nCr = nCr * (n - k) // (k + 1)

    print(_sum % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int

    solve(N, M, K)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

mod=998244353


def do():
    
    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=INTM()
    
    ans=0
    
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    for i in range( 2, n  ):
        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):
        temp=m
        for _ in range(n-1-i):
            temp=(temp*(m-1))%mod
            #print(_,m-1)
        temp=temp*cmb(n-1,i,mod)%mod
        #print(cmb(n-1,i,mod))
        ans+=temp
        ans=ans%mod
    print(ans)
    
if __name__ == '__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys
import functools
import math

sys.setrecursionlimit(100000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 998244353  # type: int


@functools.lru_cache(maxsize=None)
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def solve(N: int, M: int, K: int):
    if N == 1:
        print(M)
        exit()
    #
    # @functools.lru_cache(maxsize=None)
    # def f(i, k):
    #     if k < 0:
    #         return 0
    #     if i == N - 1:
    #         return M - 1 if k == 0 else M
    #     if i == 0:
    #         return M * f(i + 1, k)
    #     # diff color + same color
    #     return (M - 1) * f(i + 1, k) + f(i + 1, k - 1)
    #
    # print(f(0, K)%MOD)
    n = N - 1
    nCr = 1
    _sum = 0
    # (M - 1) ** (N - k - 1)
    e = [1]
    for i in range(N):
        e.append(e[-1] * (M - 1) % MOD)
    # print('ok')
    for k in range(K + 1):
        # print(nCr)
        _sum += M * e[N - k - 1] * nCr
        # print(nCr%MOD, comb(N - 1, k)%MOD)
        nCr = nCr * (n - k) // (k + 1)

    print(_sum % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int

    solve(N, M, K)


if __name__ == '__main__':
    main()

Submission status: 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)


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

fn = lf[-1]


lc = []  # n - 1 C i
for i in range(n):
    d = (lf[i] * lf[n - 1 - i]) % MOD
    dinv = power(d, MOD - 2, MOD)
    c = (fn * dinv) % MOD
    lc.append(c)


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 += n_pattern(i)


print(answer % MOD)

Submission status: Time Limit Exceeded

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

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

ans = 0

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

Submission status: Time Limit Exceeded

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

MOD = 998244353

def mod(n):         
  return n % MOD

def modpow(a, n):   #mod(a**n)を高速で求める
    res = 1  
    digit = len(str(bin(n))) - 2
    for i in range(digit):
      if (n >> i) & 1:
        res *= mod(a)
        res = mod(res)
      a = mod(a**2)
    return mod(res)
  
def inverse(a):     #aの逆元を求める
  return modpow(a, MOD-2)

MAX = 1000000           #適当な数を入力
fac, finv, inv = [[0]*MAX for i in range(3)]
def combinit():     #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 modcomb(n, k):      #mod(nCk)を計算、ただしn<MAX
  if (n < k):
    return 0
  if (n < 0 or k < 0):
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
combinit()          #下準備の実行 O(MAX)

ans = 0
for i in range(k+1):
  ans += mod(m*modpow(m-1, n-1-i)*modcomb(n-1, i))
  
print(mod(ans))