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:
from functools import reduce
import math
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)
    return x % m
def modmul(a,b):
    return a * b % 998244353
def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(modmul, range(n, n - r, -1))
    under = reduce(modmul, range(1,r + 1))
    return over * modinv(under, 998244353)
def mempow(a,b):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % 998244353
        yield temp

N,M,K = (int(x) for x in input().split())
ans = 0
if M == 1:
    if K + 1 < N:
        print('0')
    else:
        print('1')
else:
    for i in range(K+1):
        ans = (ans + (comb(N-1,i)*M*pow(M-1,N-i-1,998244353))) % 998244353
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import math
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)
    return x % m
def modmul(a,b):
    return a * b % 998244353
def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(modmul, range(n, n - r, -1))
    under = reduce(modmul, range(1,r + 1))
    return over * modinv(under, 998244353)
def mempow(a,b):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % 998244353
        yield temp

N,M,K = (int(x) for x in input().split())
mem = []
mappend = mem.append
for x in mempow(M-1,N-1):
    mappend(x)
ans = 0
if M == 1:
    if K + 1 < N:
        print('0')
    else:
        print('1')
else:
    for i in range(K+1):
        ans = (ans + (comb(N-1,i)*M*pow(M-1,N-i-1,998244353))) % 998244353
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import math
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)
    return x % m
def modmul(a,b):
    return a * b % 998244353
def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(modmul, range(n, n - r, -1))
    under = reduce(modmul, range(1,r + 1))
    return over * modinv(under, 998244353)
def mempow(a,b):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % 998244353
        yield temp

N,M,K = (int(x) for x in input().split())
mem = []
mappend = mem.append
for x in mempow(M-1,N-1):
    mappend(x)
ans = 0
if M == 1:
    if K + 1 < N:
        print('0')
    else:
        print('1')
else:
    for i in range(K+1):
        ans = (ans + (comb(N-1,i)*M*mem[N-i-1])) % 998244353
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
##through permutations and combinations we can reduce ans to
##  Summation N-1CK(m-1)^(N-1-K)


import sys
sys.setrecursionlimit(100000000)
DP={}
mod=998244353
def getproduct(M,n):
    #product=(M-1)^n
    global mod
    fact=1000
    if n<fact:
        return (M**n)%mod
    else:
        Q=int(n/fact)
        R=n%fact
        prev=1
        for q in range(Q):
            prev=(prev*((M**fact)%mod))%mod
        prev=prev*((M**R)%mod)
        return prev%mod
def ncr(n, r, p): 
    # initialize numerator 
    # and denominator 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * pow(den,  
            p - 2, p)) % p 
  
def G(N,M,K):
    global mod
    res=0
    for k in range(K+1):
        res=(res+((ncr(N-1,k,mod))%mod *(M*getproduct(M-1,N-k-1))%mod)%mod)%mod
    return res%mod

def F(curr,N,M,K):
    global DP
    if(curr,K) in DP:
        return DP[(curr,K)]
    if curr==N:
        return 1
    if curr==0:
        return M*F(curr+1,N,M,K)
    else:
        a=0
        if K>0:
            a=F(curr+1,N,M,K-1)
        b=(M-1)*F(curr+1,N,M,K)
        DP[(curr,K)]=a+b
        return a+b
N,M,K=map(int,input().strip().split())
#print(F(0,N,M,K)%mod)
print(G(N,M,K))

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import math
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)
    return x % m
def modmul(a,b):
    return a * b % 998244353
def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(modmul, range(n, n - r, -1))
    under = reduce(modmul, range(1,r + 1))
    return over * modinv(under, 998244353)
def mempow(a,b):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % 998244353
        yield temp

N,M,K = (int(x) for x in input().split())
mem = []
for x in mempow(M-1,N-1):
    mem.append(x)
ans = 0
if M == 1:
    if K + 1 < N:
        print('0')
    else:
        print('1')
else:
    for i in range(K+1):
        ans = (ans + (comb(N-1,i)*M*mem[N-i-1])) % 998244353
    print(ans)

Submission status: Time Limit Exceeded

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

  
kk=n-k
#print(kk)
color=m*(m-1)**(kk-1)%mod
#print(color)
com=math.factorial(n-1)//(math.factorial(n-kk)*math.factorial(kk-1))
while kk<=n:
  now=color
  color=color*(m-1)%mod
  now=now*(com%mod)%mod
  com=com*(n-kk)//kk
  kk+=1
  ans+=now
  ans=ans%mod
  #print(kk)
  #print(now)
  #print("color",color,"com",com)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

def getInvs(n, MOD):
    invs = [1] * (n+1)
    for x in range(2, n+1):
        invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
    return invs
invs = getInvs(K+3, MOD)

POW = [1]
for i in range(1,N):
    a = (POW[-1] * (M-1))%MOD
    POW.append(a)

mole = 1
deno = 1
for i in range(K+1):
    SUM += M * POW[N-1-i]%MOD * mole % MOD * deno % MOD
    SUM %= MOD
    mole *= (N-1-i)
    mole %= MOD
    deno *= invs[i+1]

print(SUM)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul #掛け算をする関数
from functools import reduce

def cmb(n,r):
    r = min(n-r,r) #nCrとnCn-rは等しいので小さい方を選ぶ
    if r == 0: return 1 #nC0 = 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())
ans = 0
col = M
mod = 998244353

for i in range(N)[::-1]:
    now = col
    # print('i:{}'.format(i))
    # print('col:{}'.format(col))
    now *= cmb(N-1,i)
    # print('cmb:{}'.format(cmb(N-1, i)))
    if i <= K:
        ans += now
        # print('\ni:{} now:{} ans:{}'.format(i, now, ans))
    col *= M-1

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math

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

POW = [1]

for i in range(1,N):
    a = (POW[-1] * (M-1))%MOD
    POW.append(a)

mole = 1
deno = 1
for i in range(K+1):
    SUM += M * POW[N-1-i]%MOD * mole % MOD * deno % MOD
    SUM %= MOD
    mole *= (N-1-i)
    mole %= MOD
    deno *= pow(i+1,MOD-2,MOD)

print(SUM)

Submission status: Time Limit Exceeded

Solution code:
import math

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

POW = [1]

for i in range(1,N):
    a = (POW[-1] * (M-1))%MOD
    POW.append(a)

mole = 1
deno = 1
for i in range(K+1):
    if N -1 - i >= 0:
        SUM += M * POW[N-1-i] * mole * deno
        SUM %= MOD
        mole *= (N-1-i)
        deno *= pow(i+1,MOD-2,MOD)

print(SUM)

Submission status: Time Limit Exceeded

Solution code:
import math

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

fact = [1]
fact_inv = [1]
for i in range(1,N+1):
    fact.append(fact[-1] * i)
    fact_inv.append(pow(fact[-1],MOD-2,MOD))

def combinations_count(n, r):
    return (((fact[n] * fact_inv[n-r])%MOD) * fact_inv[r])%MOD

POW = [1]

for i in range(1,N):
    a = (POW[-1] * (M-1))%MOD
    POW.append(a)

# print(POW)
# print(POW[-1])
# print(pow(M-1,N-1,MOD))
# fact = 1#fact_(N-1)
# for i in range(N):
#     fact *= i
#     fact %= MOD




for i in range(K+1):
    if N -1 - i >= 0:
        SUM += M * POW[N-1-i] * combinations_count(N-1,i)
        SUM %= MOD

print(SUM)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def nck(n, k, mod):
    bunbo = bunshi = 1
    for i in range(k):
        bunshi = (bunshi * (n-i)) % mod
        bunbo = (bunbo * (i+1)) % mod
    return (bunshi * pow(bunbo, mod-2, mod)) % mod


mod = 998244353
n, m, k = list(map(int, input().split()))
ans = m*pow(m-1, n-1, mod)
pow_ = pow((m-1), (n-(k+1)), mod)

for _k in reversed(range(1, k+1)):
    # print(n-_k-1)
    tmp = (m*pow_*nck(n-1, _k, mod)) % mod
    # print(pow_/pow((m-1), (n-_k-1), mod))
    # tmp = (m*pow((m-1), (n-_k-1), mod)*nck(n-1, _k, mod)) % mod
    pow_ = (pow_ * (m-1)) % mod
    ans += tmp
print(ans % mod)

# print((pow(m, k+1, mod)*pow(m-1, n-k-1, mod)*nck(n-1, k, mod)) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import os

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

def comb(n,k):
    nCk = 1
    MOD = 998244353

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

    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk

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

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

    print(ans%mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


fact = [1] * (N+1) # 階乗を格納するリスト
def inv(n): # MODを法とした逆元
    return pow(n, MOD-2, MOD)
for i in range(N):
    fact[i+1] = fact[i] * (i+1) % MOD # 階乗を計算

def nCk(n,k): # 組み合わせ(MOD)を返却する
    return fact[n] * inv(fact[n-k]) * inv(fact[k]) % MOD

def solve(k):
    r = M * pow(M-1,N-1-k,MOD)
    r *= nCk(N-1,k)
    return r

for k in range(K+1):
    ans += solve(k)
    ans %= MOD
print (ans)

Submission status: Time Limit Exceeded

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


fact = [1] * (N+1) # 階乗を格納するリスト
def inv(n): # MODを法とした逆元
    return pow(n, MOD-2, MOD)
for i in range(N):
    fact[i+1] = fact[i] * (i+1) % MOD # 階乗を計算

def nCk(n,k): # 組み合わせ(MOD)を返却する
    return fact[n] * inv(fact[n-k]) * inv(fact[k]) % MOD

def solve(k):
    r = M * pow(M-1,N-1-k,MOD)

    r %= MOD
    r *= nCk(N-1,k)
    r %= MOD
    return r

for k in range(K+1):
    ans += solve(k)
    ans %= MOD
print (ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def nck(n, k, mod):
    bunbo = bunshi = 1
    for i in range(k):
        bunshi = (bunshi * (n-i)) % mod
        bunbo = (bunbo * (i+1)) % mod
    return (bunshi * pow(bunbo, mod-2, mod)) % mod


mod = 998244353
n, m, k = list(map(int, input().split()))
ans = m*pow(m-1, n-1, mod)
for _k in range(1, k+1):
    tmp = (m*pow(m-1, n-_k-1, mod)*nck(n-1, _k, mod)) % mod
    ans += tmp
print(ans % mod)

# print((pow(m, k+1, mod)*pow(m-1, n-k-1, mod)*nck(n-1, k, mod)) % mod)

Submission status: Time Limit Exceeded

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

def comb(p, q):
    return math.factorial(p) // (math.factorial(q) * math.factorial(p-q))

ans = 0

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

input = sys.stdin.readline

mod = 998244353
N = 2 * 10 ** 5 + 5

fact = [1 for _ in range(N + 1)]

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

invfact = [1 for _ in range(N + 1)]

invfact[N] = pow(fact[N], mod - 2, mod)
for i in range(N, 0, -1):
	invfact[i - 1] = (invfact[i] * i ) % mod; 

def nCr(n, r):
	return fact[n] * invfact[r] % mod * invfact[n - r] % mod;

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

sum = 0
for p in range(n - k, n + 1):
	ways = m * pow(m - 1, p - 1)
	ways %= mod
	ways *= nCr(n - 1, p - 1)
	ways %= mod
	sum += ways
sum %= mod
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import sys
l = sys.stdin.readline().strip()
N, M, K = map(int, l.split())
comb_quick = {}
mod = 998244353
C = [1]
for i in range(1, (N-1) // 2 + 2):
    next = C[-1] * (N-i) // i
    C.append(next)

res = 0

exp_quick = [1]
for i in range(N):
    exp_quick.append(exp_quick[-1] * (M-1) % mod)

for x in range(0,K+1):
    crt =  exp_quick[N-x-1] * M
    crt %= mod
    #print("start")
    idx = min(x, N-1-x)
    crt *= C[idx]
    #print("end")
    crt %= mod
    res += crt
    res %= mod

print(res)

Submission status: Time Limit Exceeded

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

MOD=998244353

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])
            result %=MOD

    return result


ans=0

for i in range(K+1):
  temp=(M*(M-1)**(N-1-i)*cmb(N-1,i))%MOD
  ans+=temp

print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int, input().split())
'''
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
'''

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=(M*(M-1)**(N-1-i)*cmb(N-1,i))%998244353
  ans+=temp

print(ans%998244353)

Submission status: Time Limit Exceeded

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

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

ans=0

for i in range(K+1):
  temp=(M*(M-1)**(N-1-i)*cmb(N-1,i))%998244353
  ans+=temp

print(ans%998244353)

Submission status: Time Limit Exceeded

Solution code:
def combi(y,x,p=998244353):
  s=fac[y]
  t=fac[x]
  u=fac[y-x]
  ans= (s* pow(t,p-2,p)*pow(u,p-2,p))%p
  return ans

###############################

N,M,K=map(int,input().split())
p=998244353
fac=[1,1]
for i in range(2,N+1):
  fac.append( (fac[-1]*i)%p )


ans=0
for i in range(0,K+1):
  R = ( (M%p) *pow(M-1,N-1-i,p) )%p
  L = combi(N-1,i)
  ans = (ans + (R*L)%p)%p
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, m, K = map(int, input().split())
buf = [[-1 for i in range(K + 1)]for j in range(N)]

for n in range(1, N + 1):
  for k in range(min(n,K+1)):
    try:
      if n == 1:
        buf[n-1][k] = m
      elif k == 0:
        buf[n-1][k] = (buf[n-2][k] * (m-1)) % 998244353
      elif k == n-1:
        buf[n-1][k] = buf[n-2][k-1]
      else:
        buf[n-1][k] = (buf[n-2][k] * (m-1) + buf[n-2][k-1]) % 998244353
    except:
      print(n,k)

res = sum(buf[N-1])%998244353
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
input = sys.stdin.readline
N, M, K = map(int, input().split())
MOD = 998244353
inv = [1] * N
FAC = factorial(N - 1) % MOD
if M == 1:
    print(1 if K == N - 1 else 0)
else:
    res = 0
    for i in range(1, N):
        inv[i] = pow(factorial(i), MOD - 2, MOD)
    for k in range(K + 1):
        # k個の○とN-k-1個の|を並べる順列
        # punc = (N-1)!/k!/(N-k-1)!
        # punc = factorial(
        #     k + (N - k - 1)) // factorial(k) // factorial(N - k - 1)
        punc = FAC
        # punc *= pow(factorial(k), MOD - 2, MOD)
        punc *= inv[k]
        punc = punc % MOD
        # punc *= pow(factorial(N - k - 1), MOD - 2, MOD)
        punc *= inv[N - k - 1]
        punc = punc % MOD
        color = M * pow(M - 1, N - k - 1, MOD)
        res += ((punc % MOD) * color) % MOD
        res = res % MOD
    print(res % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
input = sys.stdin.readline
N, M, K = map(int, input().split())
MOD = 998244353
if M == 1:
    print(1 if K == N - 1 else 0)
else:
    res = 0
    for k in range(K + 1):
        # k個の○とN-k-1個の|を並べる順列
        # punc = (N-1)!/k!/(N-k-1)!
        # punc = factorial(
        #     k + (N - k - 1)) // factorial(k) // factorial(N - k - 1)
        punc = factorial(N - 1) % MOD
        punc *= pow(factorial(k), MOD - 2, MOD)
        punc = punc % MOD
        punc *= pow(factorial(N - k - 1), MOD - 2, MOD)
        punc = punc % MOD
        color = M * pow(M - 1, N - k - 1, MOD)
        res += ((punc % MOD) * color) % MOD
        res = res % MOD
    print(res % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
input = sys.stdin.readline
N, M, K = map(int, input().split())
if M == 1:
    print(1 if K == N - 1 else 0)
else:
    res = 0
    for k in range(K + 1):
        # k個の○とN-k-1個の|を並べる順列
        punc = factorial(
            k + (N - k - 1)) // factorial(k) // factorial(N - k - 1)
        # color = M * ((M - 1)**(N - k - 1))
        color = M
        for _ in range(N - k - 1):
            color *= M - 1
            color = color % 998244353
        res += ((punc % 998244353) * (color % 998244353)) % 998244353
        res = res % 998244353
    print((res) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, p):
    return (fac[n] * pow(fac[r], p - 2, p) * pow(fac[n - r], p - 2, p)) % p


p = 998244353
N, M, K = map(int, input().split())
fac = [1] * (N + 1)
for i in range(1, N + 1):
    fac[i] = (fac[i - 1] * i) % p

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

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, p):
    return (fac[n] * pow(fac[r], p - 2, p) * pow(fac[n - r], p - 2, p)) % p


p = 998244353
N, M, K = map(int, input().split())
fac = [1] * (max(N, M) + 1)
for i in range(1, max(N, M) + 1):
    fac[i] = (fac[i - 1] * i) % p

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
input = sys.stdin.readline
N, M, K = map(int, input().split())
if M == 1:
    print(1 if K == N - 1 else 0)
else:
    res = 0
    for k in range(K + 1):
        # k個の○とN-k-1個の|を並べる順列
        punc = factorial(k + (N - k - 1)) // (factorial(k)
                                              * factorial(N - k - 1))
        color = M * ((M - 1)**(N - k - 1))
        res += punc * color
    print((res) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰回数の上限を変更
from collections import deque
import itertools

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

ans=0
for i in range(K+1):
    l=list(itertools.combinations(range(N-1),i))
    #list(itertools.combinations([1,2,3,4],2))
    # -> [(1,2),(1,3),...,(2,4),(3,4)]
    ans+=(((M*len(l))%MOD )*pow(M-1,N-(i+1),MOD))%MOD

print(ans%MOD)

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

Submission status: Time Limit Exceeded

Solution code:
# E

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

import scipy.special
res = 0
for k in range(K+1):
    res += M * (M - 1) ** (N - 1 - k) * scipy.special.comb(N-1, k, exact=True)

print(res % 998244353)

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
if M != 1:
  mi = modinv(M-1,m)
else:
  mi = 0
A = M * pow(M-1,N-1,m)
for k in range(K+1):
  if k>0:
    B = B*(N-k)//k 
  res = (res+ A*B)%m
  A = (A*mi)%m
print (res)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

    def __str__(self):
        return str(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 __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 make_combination(n):
        fact = [1, 1]
        factinv = [1, 1]
        inv = [0, 1]

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

        comb = [0 for i in range(n+1)]
        for r in range(n+1):
            comb[r] = fact[n] * factinv[r] * factinv[n-r] % MOD

        return list(map(ModInt, comb))


N, M, K = map(int, input().split())
comb = ModInt.make_combination(N-1)

ans = 0
tmp = M

for x in range(N-1, -1, -1):
    if x <= K:
        ans += comb[x]*tmp
    tmp *= (M-1)

print(ans)

Submission status: Time Limit Exceeded

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

MOD = 998244353

class FermatCombination():
    def __init__(self, size, mod):
        self.mod = mod
        self.factrial = [1]
        self.inverse = [1]
        for i in range(1, size + 1):
            self.factrial.append(self.factrial[i - 1] * i % self.mod)
            self.inverse.append(self.modpow(self.factrial[i], self.mod - 2) % self.mod)

    def modpow(self, x, n):
        ret = 1
        while (n > 0):
            if n & 1:
                ret = ret * x % self.mod
            x = x * x % self.mod
            n >>= 1
        return ret

    def combine(self, n, k):
        return (self.factrial[n] * self.inverse[k] % self.mod) * self.inverse[n - k] % self.mod

fermat = FermatCombination(n + 5, MOD)

ans = 0
colors = m
for i in range(n):
    if (n-i-1 <= k):
        ans += (colors * fermat.combine(n-1, n-i-1)) % MOD
        ans %= MOD
    colors *= m-1
    colors %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
#mod = 10**9 + 7

mod=998244353


n,m,k=MI()
beki=[0 for i in range(n)]
beki[0]=m%mod
for i in range(n-1):
    beki[i+1]=(beki[i]*(m-1))%mod
    
def cmod(n, r, p):
    x,y  = 1, 1
    for i in range(r):
        x = x * (n - i) % p
        y = y * (r - i) % p
    return (x * pow(y, p - 2, p)) % p
ans=0

for i in range(k+1):
    j=n-i-1
    ans+=(beki[j]*cmod(n-1,i,mod))%mod
    #print(beki[j]*cmod(n-1,i,mod))
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

def power(x, a):
    if a == 0:
        return 1
    elif a == 1:
        return x
    elif a % 2 == 0:
        return power(x, a//2) **2 % mod
    else:
        return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
    return power(x, mod-2)

def binomial_coefficients(n, k):
    numera = 1  # 分子
    denomi = 1  # 分母

    for i in range(k):
        numera *= n-i
        numera %= mod
        denomi *= i+1
        denomi %= mod
    return numera * modinv(denomi) % mod



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

Submission status: Time Limit Exceeded

Solution code:
def main():
    from builtins import pow

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

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

    def mcomb(n, k):
        if n == 0 and k == 0:
            return 1
        if n < k or k < 0:
            return 0
        return fac[n] * pow(fac[n - k], 998244351, 998244353) * pow(fac[k], 998244351, 998244353) % 998244353

    result = 0
    for i in range(K + 1):
        result += mcomb(N - 1, i) * pow(M - 1, N - 1 - i, 998244353)
        result %= 998244353
    result *= M
    result %= 998244353
    print(result)


main()

Submission status: Time Limit Exceeded

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

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

    def mcomb(n, k, fac):
        if n == 0 and k == 0:
            return 1
        if n < k or k < 0:
            return 0
        return fac[n] * pow(fac[n - k], 998244351, 998244353) * pow(fac[k], 998244351, 998244353) % 998244353

    result = 0
    for i in range(K + 1):
        result += mcomb(N - 1, i, fac) * pow(M - 1, N - 1 - i, 998244353)
        result %= 998244353
    result *= M
    result %= 998244353
    print(result)


main()

Submission status: Time Limit Exceeded

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

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

    def mcomb(n, k):
        if n == 0 and k == 0:
            return 1
        if n < k or k < 0:
            return 0
        return fac[n] * pow(fac[n - k], 998244351, 998244353) * pow(fac[k], 998244351, 998244353) % 998244353

    result = 0
    for i in range(K + 1):
        result += mcomb(N - 1, i) * pow(M - 1, N - 1 - i, 998244353)
        result %= 998244353
    result *= M
    result %= 998244353
    print(result)


main()

Submission status: Time Limit Exceeded

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

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

    def mcomb(n, k, fac):
        if n == 0 and k == 0:
            return 1
        if n < k or k < 0:
            return 0
        return fac[n] * pow(fac[n - k], 998244351, 998244353) * pow(fac[k], 998244351, 998244353) % 998244353

    result = 0
    for i in range(K + 1):
        result += M * mcomb(N - 1, i, fac) * pow(M - 1, N - 1 - i, 998244353)
        result %= 998244353
    print(result)


main()