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: Runtime Error

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

count = 0
count_tmp = m*((m-1)**(n-1))
count += count_tmp

for i in range(1,k+1):
    count_tmp = count_tmp //(m-1) * ((n-1)-(i-1))//i
    count_tmp %= mod
    count += count_tmp
    count %= mod

print(count)

Submission status: Runtime Error

Solution code:
import math
md=998244353
def c(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % md

mod = md 
N = 2*10**5+100
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def p(x,y):
  ly=int(math.log2(y))
  d=[x]
  for i in range(ly):
    d.append((d[-1]**2)%md)
  s=1
  for i in range(ly+1):
    if y & 2**i:
      s=(s*d[i])%md
  return s
    
n,m,k=list(map(int,input().split()))


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

Submission status: Runtime Error

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

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

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

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

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

p = 998244353

comb = Combination(N-1,p)

# 何個を同じ色の組にするか0~K
cnt = 0
for k in range(K+1):
    buf = 0
    # N-1個の組のうちどれを同じ色にするかN-1Ck
    buf = comb(N-1,k)

    # それぞれで、N-k個を別の色の順列にする
    # M*(M-1)**(N-k-1)
    buf *= M
    buf *= pow((M-1),(N-k-1),p)
    buf %= p
    cnt += buf
    cnt %= p

print(cnt)

Submission status: Runtime Error

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

count = 0
count_tmp = m*((m-1)**(n-1))
count += count_tmp

for i in range(1,k+1):
    count_tmp = count_tmp //(m-1) * ((n-1)-(i-1))//i
    count += count_tmp

print(count%998244353)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

MAX_N=10**6

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

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

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

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

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

    for i in range(2,num):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

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


COMinit(MAX_N)

ans=0

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

Submission status: Runtime Error

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


class Combination:
    """
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv


mod = 998244353
total = 0
comb = Combination(n-1, mod)

v2 = [0] * (k+1)
v2[k] = (m * pow(m-1, n-k-1, mod)) % mod
for i in range(k-1, -1, -1):
    v2[i] = (v2[i+1] * (m-1)) % mod

for i in range(k+1):
    v = comb(n-1, i)
    total += (v * v2[i]) % mod
    total %= mod

print(total)

Submission status: Runtime Error

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


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

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

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

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

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

    for i in range(2,num):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

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


COMinit(N)

ans=0

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

Submission status: Runtime Error

Solution code:
X = 998244353

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

def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

inv_cache = [1]
for i in range(1, K + 1):
	inv_cache.append(calc_inverse(i, X))

inv_f_cache = [1]
d = 1
for i in range(1, K + 1):
	d = (d * inv_cache[i]) % X
	inv_f_cache.append(d)

f_cache = [1]
c = 1
for i in range(N - 1, N - M, -1):
	c = (c * i) % X
	f_cache.append(c)

#print(f_cache, inv_f_cache)

def C(n, m):
#	if m in f_cache:
#		c = f_cache[m]
#	else:
#		c = 1
#		for i in range(n - m + 1, n + 1):
#			c = (c * i) % X
#		f_cache[m] = c
#	d = 1
#	for i in range(1, m + 1):
#		d = (d * inv_cache[i]) % X
	return (f_cache[m] * inv_f_cache[m]) % X


total = 0
for k in range(K + 1):
	total = (total + M * pow(M - 1, N - 1 - k, X) * C(N - 1, k)) % X
	
#	print(k, M * pow(M - 1, N - 1 - k, X))
	

print(total)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m,k = map(int, input().split())
mod = 998244353
ans = 0
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
#a/b = a*(b`)となるb`を求める
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod
combi = [0 for i in range(n)]
combi[0] = 1
combi[1] = n-1
for i in range(2,n):
    combi[i] = (combi[i-1]*(n-i)*mod_inv(i,mod)) % mod
for i in range(k+1):
    plus = m * pow(m-1,n-1-i,mod)
    plus *= combi[n-i-1]
    plus %= mod
    ans += plus
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
    A[i] -= 1
li = [False] * N
f = True
now = 0
l = []
l2 = [0] * N
i = 0
while f:
    l.append(now)
    li[now] = True
    l2[now] = i
    if li[A[now]]:
        f = False
        num = len(l) - l2[A[now]]
        n = l2[A[now]]
    i += 1
    now = A[now]
k = (K-n) % num
print(l[min(K, n+k)]+1)

Submission status: Runtime Error

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 998244353
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return ( m + x%m ) % m
    
def nCk(n,k):
    res = 1
    a=n-k
    b=k
    for i in range(1,a+b+1):
        res = res*i%mod
    for i in range(1,a+1):
        res = res*mod_inv(i,mod)%mod
    for i in range(1,b+1):                                 
        res = res*mod_inv(i,mod)%mod
    return res

def main():
    n,m,k = inpm()
    if k == 0:
        print((m*pow(m-1,n-1,mod))%mod)
        return
    ans = 0
    a = (m*pow(m-1,n-1,mod))%mod
    b = 1
    x = mod_inv(m-1,mod)
    for i in range(k+1):
        ans += (a*b)%mod
        ans %= mod
        a = a*x%mod
        b = b*(n-1-i)%mod
        b = b*mod_inv(i+1,mod)%mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>

using namespace std;

typedef long long i64;
typedef i64 int_t;
typedef vector<int_t> vi;
typedef vector<vi> vvi;

typedef pair<int_t, int_t> pi;

#define tr(c, i) for(auto i = (c).begin(); i != (c).end(); i++)
#define pb push_back
#define sz(a) i64((a).size())
#define all(c) (c).begin(), (c).end()
#define REP(s, e, i) for(i=(s); i < (e); ++i)

i64 NUM = 998244353;

i64 modpow(i64 a, i64 b) {
  i64 ans = 1;
  while(b != 0) {
    if(b % 2 == 1) {
      ans *= a;
      ans %= NUM;
    }
    a = a * a;
    a %= NUM;
    b /= 2;
  }
  return ans;
}

i64 modinv(i64 a) {
  return modpow(a, NUM-2);
}

int main(int argc, char *argv[]) {
  i64 N, M, K, i;
  cin >> N >> M >> K;

  vi factorial(N), inv_factorial(N);
  factorial[0] = factorial[1] = 1;
  inv_factorial[0] = inv_factorial[1] = 1;

  REP(2, N, i) {
    factorial[i] = (factorial[i-1] * i) % NUM;
    inv_factorial[i] = modinv(factorial[i]);
  }

  i64 ans = 0, k;
  REP(0, K+1, k) {
    i64 da = factorial[N-1];
    
    da *= inv_factorial[k];
    da %= NUM;
    
    da *= inv_factorial[N-1-k];
    da %= NUM;
    
    da *= M;
    da %= NUM;
    
    da *= modpow(M-1, N-k-1);
    da %= NUM;

    ans += da;
    ans %= NUM;
  }
  cout << ans << endl;

  return 0;
}

Submission status: Runtime Error

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 998244353
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return ( m + x%m ) % m
    
def nCk(n,k):
    res = 1
    a=n-k
    b=k
    for i in range(1,a+b+1):
        res = res*i%mod
    for i in range(1,a+1):
        res = res*mod_inv(i,mod)%mod
    for i in range(1,b+1):                                 
        res = res*mod_inv(i,mod)%mod
    return res

def main():
    n,m,k = inpm()
    ans = 0
    a = (m*pow(m-1,n-1,mod))%mod
    b = 1
    x = mod_inv(m-1,mod)
    for i in range(k+1):
        ans += (a*b)%mod
        ans %= mod
        a = a*x%mod
        b = b*(n-1-i)%mod
        b = b*mod_inv(i+1,mod)%mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,m,k = map(int,input().split())
mod = 998244353
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y
#print(inv(2))
now = m
for _ in range(n-1):
  now *= m-1
  now %= mod
ans = int(now)
for i in range(k):
  now *= inv(m-1)
  now *= n-1-i
  now *= inv(i+1)
  now %= mod
  #print(now)
  ans += now
  ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
 a,b,c = int(input().split())
  n = a,b,c.itertools()
print(n)