Problem:


Score : 700 points

Problem Statement

Takahashi throws N dice, each having K sides with all integers from 1 to K. The dice are NOT pairwise distinguishable.
For each i=2,3,...,2K, find the following value modulo 998244353:

The number of combinations of N sides shown by the dice such that the sum of no two different sides is i.

Note that the dice are NOT distinguishable, that is, two combinations are considered different when there exists an integer k such that the number of dice showing k is different in those two.

Constraints

1 \leq K \leq 2000

2 \leq N \leq 2000

K and N are integers.

Input

Input is given from Standard Input in the following format:

K N

Output

Print 2K-1 integers. The t-th of them (1\leq t\leq 2K-1) should be the answer for i=t+1.

Sample Input 1

3 3

Sample Output 1

7
7
4
7
7

For i=2, the combinations (1,2,2),(1,2,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3) satisfy the condition, so the answer is 7.

For i=3, the combinations (1,1,1),(1,1,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3) satisfy the condition, so the answer is 7.

For i=4, the combinations (1,1,1),(1,1,2),(2,3,3),(3,3,3) satisfy the condition, so the answer is 4.

Sample Input 2

4 5

Sample Output 2

36
36
20
20
20
36
36

Sample Input 3

6 1000

Sample Output 3

149393349
149393349
668669001
668669001
4000002
4000002
4000002
668669001
668669001
149393349
149393349



Sample input:
3 3


Sample output:
7
7
4
7
7

Submission status: Time Limit Exceeded

Solution code:
mod  = 998244353

def add(a,b):
    a += b
    if (a >= mod):
        a -= mod
    return  a
def sub(a,b):
    a -= b
    if (a < 0):
        a += mod
    return  a
def mul(a,b):   return  a * b % mod
def Pow(a,b):
    ans = 1
    while (b):
        if(b & 1):  ans = mul(ans,a)
        a   = mul(a,a)
        b >>= 1
    return  ans

k, n = map(int,input().split())
size = n + k

Fac = [1]
Inv = [1]
Pw2 = [1]

for i in range(1,size + 1):
    Pw2.append(mul(Pw2[i - 1],2))
    Fac.append(mul(Fac[i - 1],i))
    Inv.append(0)

Inv[size] = Pow(Fac[size],mod - 2)

for i in reversed(range(1,size)):
    Inv[i] = mul(Inv[i + 1],i + 1)

def Ckn(a,b):
    if (a < b): return  0
    if (b < 0): return  0
    return  mul(Fac[a],mul(Inv[b],Inv[a - b]))

for i in range(2,k + k + 1):
    cnt = min(k,i - 1) - max(1,i - k) + 1
    ans = 0

    for j in range(0,(cnt // 2) + 1):
        val = mul(Ckn(cnt // 2,j),Pw2[j])

        ans = add(ans,mul(Ckn(n - 1 + k - cnt,j + k - cnt - 1),val))

        if (i % 2 == 1):
            continue

        ans = add(ans,mul(Ckn(n - 2 + k - cnt,j + k - cnt - 1),val))

    print(ans)

Submission status: Time Limit Exceeded

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

# K+1 - x でうつす -> i と 2K+2-i は同じ

MOD = 998244353
U = 10000
fact = [1] * (U+1)
fact_inv = [1] * (U+1)
for n in range(1,U+1):
    fact[n] = fact[n-1] * n % MOD
fact_inv[n] = pow(fact[n], MOD-2, MOD)
for n in range(U,0,-1):
    fact_inv[n-1] = fact_inv[n] * n % MOD

def comb(n,k):
    if not (0 <= k <= n):
        return 0
    return fact[n] * fact_inv[k] * fact_inv[n-k] % MOD

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

def F(x,y,N):
    n = min(x, N)
    return sum(comb(x,i) * pow(2,i,MOD) * comb(N+y-1,i+y-1) for i in range(n+1)) % MOD

answer = []
for S in range(2,K+2):
    if S & 1:
        x = F((S-1)//2, K - S + 1, N)
    else:
        x = F((S-1)//2, K - S + 1, N) + F((S-1)//2, K - S + 1, N - 1)
    answer.append(x % MOD)

answer += answer[:-1][::-1]

print('\n'.join(map(str,answer)))

Submission status: Time Limit Exceeded

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

# K+1 - x でうつす -> i と 2K+2-i は同じ

MOD = 998244353
U = 10000
fact = [1] * (U+1)
fact_inv = [1] * (U+1)
for n in range(1,U+1):
    fact[n] = fact[n-1] * n % MOD
fact_inv[n] = pow(fact[n], MOD-2, MOD)
for n in range(U,0,-1):
    fact_inv[n-1] = fact_inv[n] * n % MOD

def comb(n,k):
    if not (0 <= k <= n):
        return 0
    return fact[n] * fact_inv[k] * fact_inv[n-k] % MOD

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

def F(x,y,N):
    # 片方しか取れないものが x ペア
    # 自由に使える枠が y ある
    n = min(x, N)
    # x ペア から、iペア使う
    cnt = 0
    for i in range(n+1):
        t = comb(x,i) # どの i ペアを使うか
        t *= pow(2,i,MOD) # i ペアのうちどっちを使うか
        # とりあえず1つずつ使う
        # あとは、a1+a2+...+a_{i+y} = N-i, a_j >= 0
        t *= comb(N+y-1,i+y-1)
        cnt += t
    cnt %= MOD
    return cnt

answer = []
for S in range(2,K+2):
    if S & 1:
        x = F((S-1)//2, K - S + 1, N)
    else:
        x = F((S-1)//2, K - S + 1, N) + F((S-1)//2, K - S + 1, N - 1)
    answer.append(x % MOD)

answer += answer[:-1][::-1]

print('\n'.join(map(str,answer)))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
K, N = map(int, input().split())
mod = 998244353
frac = [1]*5010
for i in range(2,5010):
    frac[i] = i * frac[i-1]%mod
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*pow(frac[b], mod-2, mod)*pow(frac[a-b], mod-2, mod)%mod
A = Counter()
def calc(x):
    if A[x]:
        return A[x]
    res = 0
    for i in range(N//2+1):
        res = (res + (-1)**i*comb(x, i)*comb(N+K-1-2*i, N-2*i))%mod
    A[x] = res
    return res
for j in range(2, 2*K+1):
    print(calc(min(j, (2*K+2-j))//2))

Submission status: Time Limit Exceeded

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

dprint = lambda *x:x

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 #出力の制限
__N = 8000
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 kumiawase(p, q):
    # dprint(p,q,cmb(p+q-1,q-1 ,mod))
    return cmb(p+q -1,q-1 ,mod)


def solve(n):
    assert n <= K+1
    # 組み合わせの組
    # abs(n-1)//2 + 偶数分 n//2?
    # 2 ->  1,1
    # 3 -> 1,2
    # 4 -> 1,3 2,2
    # 5 -> 1,4 2,3
    # 6 -> 1,5 2,4 3,3
    # 7  3通り

    # 組のうち片方だけ使用する数 p
    ans = 0
    kumi = (n - 1) // 2
    for p in range(kumi+1):
        # dprint("p",p,"n",n)
        if p>N:
            break
        # 使えるのは p個 + 組に関係ないやつ
        ans += 2**p *cmb(kumi,p,mod)* kumiawase(N - p, p+ (K-kumi*2- int(n%2==0) ) )
        # dprint("anstmp1",ans)
        if n % 2 == 0 and N - p -1 >= 0:
            ans += 2**p *cmb(kumi,p,mod) * kumiawase(N - p -1 , p+ (K-kumi*2- int(n%2==0) ) ) # K==n//2を使用
    # dprint("-------",ans)
    return ans


ans = []
for i in range(2, 2 * K +1):
    if i <= K+1:
        tmp = solve(i)%998244353
        ans.append(tmp)
        print(tmp)
    else:
        print(ans[-i + K])

Submission status: Time Limit Exceeded

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

dprint = lambda *x:x

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 #出力の制限
__N = 4000
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 kumiawase(p, q):
    # dprint(p,q,cmb(p+q-1,q-1 ,mod))
    return cmb(p+q -1,q-1 ,mod)


def solve(n):
    assert n <= K+1
    # 組み合わせの組
    # abs(n-1)//2 + 偶数分 n//2?
    # 2 ->  1,1
    # 3 -> 1,2
    # 4 -> 1,3 2,2
    # 5 -> 1,4 2,3
    # 6 -> 1,5 2,4 3,3
    # 7  3通り

    # 組のうち片方だけ使用する数 p
    ans = 0
    kumi = (n - 1) // 2
    for p in range(kumi+1):
        # dprint("p",p,"n",n)
        if p>N:
            break
        # 使えるのは p個 + 組に関係ないやつ
        ans += 2**p *cmb(kumi,p,mod)* kumiawase(N - p, p+ (K-kumi*2- int(n%2==0) ) )
        # dprint("anstmp1",ans)
        if n % 2 == 0 and N - p -1 >= 0:
            ans += 2**p *cmb(kumi,p,mod) * kumiawase(N - p -1 , p+ (K-kumi*2- int(n%2==0) ) ) # K==n//2を使用
    # dprint("-------",ans)
    return ans


ans = []
for i in range(2, 2 * K +1):
    if i <= K+1:
        tmp = solve(i)%998244353
        ans.append(tmp)
        print(tmp)
    else:
        print(ans[-i + K])

Submission status: Time Limit Exceeded

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

dprint = lambda *x:x

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 #出力の制限
__N = 4000
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 kumiawase(p, q):
    dprint(p,q,cmb(p+q-1,q-1 ,mod))
    return cmb(p+q -1,q-1 ,mod)


def solve(n):
    assert n <= K+1
    # 組み合わせの組
    # abs(n-1)//2 + 偶数分 n//2?
    # 2 ->  1,1
    # 3 -> 1,2
    # 4 -> 1,3 2,2
    # 5 -> 1,4 2,3
    # 6 -> 1,5 2,4 3,3
    # 7  3通り

    # 組のうち片方だけ使用する数 p
    ans = 0
    kumi = (n - 1) // 2
    kumi_include_half = kumi+int(n%2==0)
    for p in range(kumi+1):
        dprint("p",p,"n",n)
        if p>N:
            break
        # 使えるのは p個 + 組に関係ないやつ
        ans += 2**p *cmb(kumi,p,mod)* kumiawase(N - p, p+ (K-kumi*2- int(n%2==0) ) )
        dprint("anstmp1",ans)
        if n % 2 == 0 and N - p -1 >= 0:
            ans += 2**p *cmb(kumi,p,mod) * kumiawase(N - p -1 , p+ (K-kumi*2- int(n%2==0) ) ) # K==n//2を使用
    dprint("-------",ans)
    return ans


ans = []
for i in range(2, 2 * K +1):
    if i <= K+1:
        tmp = solve(i)%998244353
        ans.append(tmp)
        print(tmp)
    else:
        print(ans[-i + K])

Submission status: Time Limit Exceeded

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

facts = [1]
invs = [1]
pow2 = [1]
for i in range(1, n+k):
    f = i*facts[i-1]%MOD
    facts.append(f)
    invs.append(pow(f, MOD-2, MOD))
    pow2.append(2**i%MOD)

def nCk(n, k):
    return (facts[n]*invs[k]*invs[n-k])%MOD
def nHk(n, k):
    return nCk(n+k-1, n-1)

ans = []
for i in range(2, k+2):
    p = i//2
    ans_i = 0
    for q in range(min(p+1, n+1)):
        if k-i+q < 0:
            continue
        if i%2 > 0: # odd
            ans_iq = pow2[q]*nCk(p, q)*nHk(k-(i-1)+q, n-q)%MOD
        else: # even
            ans_iq = 0
            if q > 0 and k-i+q > 0:
                ans_iq = (ans_iq+pow2[q-1]*nCk(p-1, q-1)*nHk(k-(i-1)+(q-1), n-q))%MOD
            if q < p:
                ans_iq = (ans_iq+pow2[q]*nCk(p-1, q)*nHk(k-(i-1)+q, n-q))%MOD
            # print(ans_iq)
        ans_i = (ans_i + ans_iq)%MOD
    ans.append(ans_i)

for a in ans+ans[-2::-1]:
    print(a)

Submission status: Time Limit Exceeded

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

facts = [1]
invs = [1]
for i in range(1, n+k):
    f = i*facts[i-1]%MOD
    facts.append(f)
    invs.append(pow(f, MOD-2, MOD))

def nCk(n, k):
    return (facts[n]*invs[k]*invs[n-k])%MOD
def nHk(n, k):
    return nCk(n+k-1, n-1)

ans = []
for i in range(2, k+2):
    p = i//2
    ans_i = 0
    for q in range(min(p+1, n+1)):
        if k-i+q < 0:
            continue
        if i%2 > 0: # odd
            ans_iq = pow(2, q, MOD)*nCk(p, q)*nHk(k-(i-1)+q, n-q)%MOD
        else: # even
            ans_iq = 0
            if q > 0 and k-i+q > 0:
                ans_iq = (ans_iq+pow(2, q-1, MOD)*nCk(p-1, q-1)*nHk(k-(i-1)+(q-1), n-q))%MOD
            if q < p:
                ans_iq = (ans_iq+pow(2, q, MOD)*nCk(p-1, q)*nHk(k-(i-1)+q, n-q))%MOD
            # print(ans_iq)
        ans_i = (ans_i + ans_iq)%MOD
    ans.append(ans_i)

for a in ans+ans[-2::-1]:
    print(a)

Submission status: Time Limit Exceeded

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


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


def H(n, k, mod):
    return cmb(n+k-1, k, mod)

Nmax = 10**5
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]

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

ans = []
for i in range(2, K+2):
    res = 0
    if i % 2 == 1:
        for j in range(i//2+1):
            res += cmb(i//2, j, mod)*2**j*H(K-i//2*2+j, N-j, mod)
            res %= mod
    else:
        for j in range(i//2):
            res += cmb(i//2-1, j, mod)*2**j*H(K-i+1+j, N-j, mod)
            res += cmb(i//2-1, j, mod)*2**j*H(K-i+1+j, N-1-j, mod)
            res %= mod
    ans.append(res)

for elem in ans + ans[-2::-1]:
    print(elem)

Submission status: Time Limit Exceeded

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

list_size = 5000

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r or r < 0:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

ans = []
for i in range(2, k+2):
	num = 0
	if i%2 == 1:
		for j in range(0, i//2+1):
			#num += comb(i//2, j) * comb(n-1, j-1) * pow(2, j, MOD) * comb(n+k-i-j, k-i)
			num += comb(i//2, j) * pow(2, j, MOD) * comb(n+k-i, k-i+j)
			num %= MOD
	else:
		for j in range(0, i//2):
			#num += comb(i//2-1, j) * comb(n-1, j-1) * pow(2, j, MOD) * comb(n+k-i-j, k-i)
			num += comb(i//2-1, j) * pow(2, j, MOD) * comb(n+k-i, k-i+j)
			#num += comb(i//2-1, j) * comb(n-2, j-1) * pow(2, j, MOD) * comb(n+k-i-j-1, k-i)
			num += comb(i//2-1, j) * pow(2, j, MOD) * comb(n+k-i-1, k-i+j)
			num %= MOD
	ans.append(num)

print(*ans, sep="\n")
ans = reversed(ans[:k-1])
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        
# 二項係数
def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if not (0<=r and r<=n):
        return 0
    
    return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod

MOD = 998244353

k,n = li()

inv = inv_mod(n+k,MOD)
fac = fact(n+k,MOD)
facInv = fact_inv(n+k,inv,MOD)

answers = []
if k == 1:
    print(0)

else:
    for t in range(2,k+2):
        p = t//2
        ans = 0
        if t%2 == 0:
            temp = 0
            for q in range(p):
                temp = temp + nCr(p-1,q,MOD,fac,facInv) \
                              * (2**q) \
                              * nCr(n+k-2*p,n-q,MOD,fac,facInv)
                temp %= MOD
                
                temp = temp + nCr(p-1,q,MOD,fac,facInv) \
                              * (2**q) \
                              * nCr(n+k-2*p-1,n-q-1,MOD,fac,facInv)
                temp %= MOD
                
            ans = temp%MOD
        
        else:
            temp = 0
            for q in range(p+1):
                temp = temp + nCr(p,q,MOD,fac,facInv) \
                              * (2**q) \
                              * nCr(n+k-2*p-1,n-q,MOD,fac,facInv)
                temp %= MOD
            
            ans = temp%MOD
            
        answers.append(ans)
        print(ans)
        
for ans in answers[-2::-1]:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
K, N = [int(i) for i in input().split(' ')]
mod = 998244353
sys.setrecursionlimit(100000)

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

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

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

def C(n, r):
    if r < 0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

olist = [C(N+K-2, N) % mod if K!=1 else 0]

def EE(i):
    k2 = int((K - abs(K - int((i-1)/2) * 2) )/2)
    k1 = K - k2*2 - (1 if i % 2 == 0 else 0)
    result = 0
    for j in range(min(k2, N+1)):
        if i % 2 == 1:
            olist[j] = div(olist[j] * k2, k2-j)
        olist[j] = div(olist[j] * (k1+j) , N+k1)
        result = (result + olist[j]) % mod
        if i % 2 == 0 and j != N:
            result = (result + div(olist[j] * (N-j), N+k1-1)) % mod

    if N >= k2:
        if i % 2 == 1:
            olist.append((C(k2, k2) * C(N+k1-1, N-k2) * pow(2, k2)) % mod)
        else:
            if i != 2:
                olist[k2] = div(olist[k2] * (k1+k2), N+k1)
            result = (result + div(olist[k2] * (N-k2), N+k1-1)) % mod
        result = (result + olist[k2]) % mod
    return result

if K == 1:
    print(0)
else:
    result = []
    for i in range(K):
        result.append(str(EE(i+2)))
    print("\n".join(result + result[:-1][::-1]))

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

K, N = reads()
MOD = 998244353

MAXN = 5000

fact = [1] * MAXN
for i in range(1, MAXN): fact[i] = (fact[i-1] * i) % MOD
invfact = [0] * MAXN; invfact[-1] = pow(fact[-1], MOD-2, MOD)
for i in range(MAXN-2, -1, -1): invfact[i] = invfact[i+1] * (i+1) % MOD
def comb(n, k):
  return fact[n] * invfact[n-k] * invfact[k] % MOD if 0 <= k <= n else 0
def h(n, k):
  return comb(n+k-1, n) if k >= 1 else 0

def solve(n, k, u):
  ans = 0
  for q in range(u+1):
    s = 2**(u-q) * h(n-u+q, k-q-u)
    # print(n, k, u, q, s)
    ans = (ans + comb(u, q) * pow(2, u-q, MOD) % MOD * h(n-u+q, k-q-u)) % MOD
  return ans

for i in range(2, 2*K+1):
  u = sum(j < i-j <= K for j in range(1, K+1))
  if i % 2 == 1:
    ans = solve(N, K, u)
  else:
    ans = (solve(N, K-1, u) + solve(N-1, K-1, u)) % MOD
  print(ans)

Submission status: Time Limit Exceeded

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

P = N+K
fact = [1]*(P+1)
rfact = [1]*(P+1)
for i in range(P):
    fact[i+1] = r = ((i+1) * fact[i]) % MOD
    rfact[i+1] = pow(r, MOD-2, MOD)

def comb(n, k):
    return fact[n] * rfact[k] * rfact[n-k] % MOD

pow2 = [1]*(P+1)
r = 1
for i in range(P):
    r = pow2[i+1] = (r * 2) % MOD

def calc(A):
    M = A//2
    r = 0
    if A % 2:
        p = K - 2*M + N - 2
        for m in range(max(0, 2*M+2-K), min(M, N-1)+1):
            r += pow2[m] * comb(M, m) * (comb(p, N-m) + comb(p-1, N-m-1)) % MOD
        if 2*M+2-K <= N <= M:
            r += pow2[N] * comb(M, N) % MOD
    else:
        p = K - 2*M + N - 1
        for m in range(max(0, 2*M+1-K), min(N, M)+1):
            r += pow2[m] * comb(M, m) * comb(p, N-m) % MOD
    return r % MOD
ans = []
for i in range(2, 2*K+1):
    if i <= K:
        ans.append(calc(i - 1))
    else:
        ans.append(calc(2*K - i + 1))
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

P = N+K
fact = [1]*(P+1)
rfact = [1]*(P+1)
for i in range(P):
    fact[i+1] = r = ((i+1) * fact[i]) % MOD
    rfact[i+1] = pow(r, MOD-2, MOD)

def comb(n, k):
    return fact[n] * rfact[k] * rfact[n-k] % MOD

def calc(A):
    M = A//2
    r = 0
    if A % 2:
        p = K - 2*M + N - 2
        for m in range(max(0, 2*M+2-K), min(M, N)+1):
            if 2*M+2-K <= m < N:
                r += pow(2, m, MOD) * comb(M, m) * (comb(p, N-m) + comb(p-1, N-m-1)) % MOD
            elif 2*M+2-K <= m == N:
                r += pow(2, m, MOD) * comb(M, m) * comb(p, N-m) % MOD
    else:
        p = K - 2*M + N - 1
        for m in range(max(0, 2*M+1-K), min(N, M)+1):
            r += pow(2, m, MOD) * comb(M, m) * comb(p, N-m) % MOD
    return r % MOD
ans = []
for i in range(2, 2*K+1):
    if i <= K:
        ans.append(calc(i - 1))
    else:
        ans.append(calc(2*K - i + 1))
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def solve_sub(k, n, p, factorials, invs):
    """Number of patterns where any pair(s) of p pairs appear when n dices are rolled"""
    ret = 0
    for q in range(1, min(p, n // 2) + 1):
        # tmp1 = factorials[p + q - 1] * invs[q] * invs[p - 1] % MOD
        tmp1 = (factorials[p] * invs[q] % MOD) * invs[p - q] % MOD
        tmp2 = (factorials[k + n - 2 * q - 1] * invs[n - 2 * q] % MOD) * invs[k - 1] % MOD
        ret += tmp1 * tmp2 * (-1) ** (q - 1)
        ret %= MOD
    return ret


def solve(k, n):
    if k == 1:
        return [0]
    factorials, invs = prepare(k + n, MOD)
    all_patterns_odd = factorials[k + n - 1] * invs[n] * invs[k - 1] % MOD
    all_patterns_even0 = factorials[k + n - 2] * invs[n] * invs[k - 2] % MOD
    all_patterns_even1 = factorials[k + n - 3] * invs[n - 1] * invs[k - 2] % MOD
    # print(all_patterns_even0, all_patterns_even1)
    buf = []

    for i in range(2, k + 2):
        pairs = i // 2 - max(0, i - k - 1)
        if i % 2 == 0:
            ans = all_patterns_even0 - solve_sub(k - 1, n, pairs - 1, factorials, invs)
            # print(solve_sub(k - 1, n, pairs - 1, factorials, invs))
            ans += all_patterns_even1 - solve_sub(k - 1, n - 1, pairs - 1, factorials, invs)
            # print(solve_sub(k - 1, n - 1, pairs - 1, factorials, invs))
            ans %= MOD
        else:
            ans = (all_patterns_odd - solve_sub(k, n, pairs, factorials, invs)) % MOD
        buf.append(ans)

    return buf


MOD = 998244353
k, n = map(int, input().split())
ans = solve(k, n)
print('\n'.join(map(str, ans)))
print('\n'.join(map(str, ans[-2::-1])))

Submission status: Time Limit Exceeded

Solution code:
k,n =map(int,input().split())
mod = 998244353
fact=[1]*5000
for i in range(1,len(fact)):
  fact[i] = fact[i-1]*i%mod
def comb(n,k,p):
  if com[n][k] != -1:
    return com[n][k]
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=fact[n]
  b=fact[k]
  c=fact[n-k]
  yey = (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
  com[n][k] = yey
  return yey
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
com = [[-1] *4050 for i in range(4050)]
for i in range(2,2*k+1):
  ans = 0
  if i %2 == 1:
    pp = (i+1)//2
    pm = i - pp
    p = min(k-pp+1,pm)
    for q in range(p+1):
      sen = comb(p,q,mod)*power_func(2,q,mod)%mod
      if n - q<0:
        continue
      r = k-p*2
      if r <0:
        r = 0
      ans += sen* comb(n+r-1,n-q,mod)%mod
    print(ans%mod)
  else:
    pp = i//2 +1
    pm = i//2 -1
    p = min(k-pp+1,pm)
    for q in range(p+1):
      sen = comb(p,q,mod)*power_func(2,q,mod)%mod
      if n - q<0:
        continue
      r = k-p*2-1
      if r <0:
        r = 0
      ans += sen* comb(n+r-1,n-q,mod)%mod
    for q in range(p+1):
      sen = comb(p,q,mod)*power_func(2,q,mod)%mod
      if n - q-1<0:
        continue
      r = k-p*2-1
      if r <0:
        r = 0
      ans += sen* comb(n+r-2,n-q-1,mod)%mod
    print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
k,n =map(int,input().split())
mod = 998244353
fact=[1]*5000
for i in range(1,len(fact)):
  fact[i] = fact[i-1]*i%mod
def comb(n,k,p):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=fact[n]
  b=fact[k]
  c=fact[n-k]
  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 i in range(2,2*k+1):
  ans = 0
  if i %2 == 1:
    pp = (i+1)//2
    pm = i - pp
    p = min(k-pp+1,pm)
    for q in range(p+1):
      sen = comb(p,q,mod)*2**q
      if n - q<0:
        continue
      r = k-p*2
      if r <0:
        r = 0
      ans += sen* comb(n+r-1,n-q,mod)
    print(ans%mod)
  else:
    pp = i//2 +1
    pm = i//2 -1
    p = min(k-pp+1,pm)
    for q in range(p+1):
      sen = comb(p,q,mod)*2**q
      if n - q<0:
        continue
      r = k-p*2-1
      if r <0:
        r = 0
      ans += sen* comb(n+r-1,n-q,mod)
    for q in range(p+1):
      sen = comb(p,q,mod)*2**q
      if n - q-1<0:
        continue
      r = k-p*2-1
      if r <0:
        r = 0
      ans += sen* comb(n+r-2,n-q-1,mod)
    print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
k,n =map(int,input().split())
mod = 998244353
fact=[1]*4010
for i in range(1,len(fact)):
  fact[i] = fact[i-1]*i%mod
def comb(n,k,p):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=fact[n]
  b=fact[k]
  c=fact[n-k]
  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 i in range(2,2*k+1):
  ans = 0
  if i %2 == 1:
    pp = (i+1)//2
    pm = i - pp
    p = min(k-pp+1,pm)
    for q in range(p+1):
      sen = comb(p,q,mod)*2**q
      if n - q<0:
        continue
      r = k-p*2
      if r <0:
        r = 0
      ans += sen* comb(n+r-1,n-q,mod)
    print(ans%mod)
  else:
    pp = i//2 +1
    pm = i//2 -1
    p = min(k-pp+1,pm)
    for q in range(p+1):
      sen = comb(p,q,mod)*2**q
      if n - q<0:
        continue
      r = k-p*2-1
      if r <0:
        r = 0
      ans += sen* comb(n+r-1,n-q,mod)
    for q in range(p+1):
      sen = comb(p,q,mod)*2**q
      if n - q-1<0:
        continue
      r = k-p*2-1
      if r <0:
        r = 0
      ans += sen* comb(n+r-2,n-q-1,mod)
    print(ans%mod)

Submission status: Time Limit Exceeded

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

MOD = 998244353

fact = [1]*200001
t = 1
for i in range(1,200001):
    t = (t*i)%MOD
    fact[i] = t

def ncr(n,r):
    return (fact[n] * pow(fact[r],MOD-2,MOD) % MOD) * pow(fact[n-r],MOD-2,MOD) % MOD

for i in range(2,2*K+1):
    t1,t2 = 0,0
    Ans = 0
    # p : 足して i になる整数の組の数
    np = i//2 - max(i-1-K,0)
    # p組からq組, 片方を使用する場合の数を足し合わせる
    # 偶奇で場合分け
    if i%2==0:
        # 偶数の場合 : 1組だけ同じ数の組があるため特別扱いする
        np -= 1
        for nq in range(np+1):
            # 同じ数の組の数字を全く含まない場合
            t1 = ncr(np,nq)*(2**nq)
            nr = K - np*2 - 1
            t2 = ncr(N+nr-1,N-nq) if N+nr-1>=N-nq else 0
            Ans += t1*t2
            # 同じ数の組の数字を1つ含む場合
            t2 = ncr(N-1+nr-1,N-1-nq) if N-1+nr-1>=N-1-nq else 0
            Ans += t1*t2
    else:
        # 奇数の場合 : p組全て互いに異なる数
        for nq in range(np+1):
            t1 = ncr(np,nq)*(2**nq)
            nr = K - np*2
            t2 = ncr(N+nr-1,N-nq) if N-1+nr-1>=N-1-nq else 0
            Ans += t1*t2
    print(Ans%MOD)

Submission status: Time Limit Exceeded

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

INV=[None]*(N+K+2)
for i in range(1,N+K+2):
    INV[i]=pow(i,mod-2,mod)
 
Combi=[None]*(N+K+1)#Combi[i]=i C (K-1) を表す
Combi[K-1]=1
for i in range(K,N+K+1):
    Combi[i]=Combi[i-1]*i *INV[i-K+1] %mod





all=Combi[N+K-1]
for i in range(2,1+K+K):
    ANS=all
    x=i//2-max(0,(i-K-1))
    CB_x=1

    j=1
    while N+K-1-j*2>=K-1 and j<=x:
        CB_x=CB_x*(x-j+1)//j
        #print(CB_x)
        ANS+=((-1)**j)*CB_x*Combi[N+K-1-j*2]
        #print(((-1)**j)*CB_x*Combi[N+K-1-j],ANS)
        ANS=ANS%mod

        j+=1
        #print(i,j,ANS)
    
    #ANS-=x*Combi[N+K-3]
    print(ANS%mod)

Submission status: Time Limit Exceeded

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

m = [[0] * 2005 for i in range(4005)]

def f():
    K, N = map(int, raw_input().split())
    MOD = 998244353

    for i in range(4001):
        m[i][0] = 1
    for i in range(2001):
        m[i][i] = 1
    for i in range(1, 4001):
        for j in range(1, 2001):
            m[i][j] = (m[i - 1][j] + m[i - 1][j - 1]) % MOD

    m2 = [1] * 4005
    for i in range(1, 4001):
        m2[i] = (m2[i - 1] * 2) % MOD

    ls = []
    for i in range(2, K + 2):
        ans = 0
        if i % 2 == 0:
            rem = i / 2 - 1
            for j in range(rem + 1):
                ans += m[N + K - 2 - rem * 2][K - 2 - rem * 2 + j] \
                * m[rem][j] * m2[j]
                ans += m[N + K - 3 - rem * 2][K - 2 - rem * 2 + j] \
                * m[rem][j] * m2[j]
                ans %= MOD
        else:
            rem = i / 2
            for j in range(rem + 1):
                ans += m[N + K - 1 - rem * 2][K - 1 - rem * 2 + j] \
                * m[rem][j] * m2[j]
                ans %= MOD
        ls.append(ans % MOD)

    ls += ls[:-1][::-1]

    for num in ls:
        print num

f()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 998244353
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

K,N = inpl()
MAX = K+N+10
fac = [1]*(MAX+1)
for i in range(1,MAX+1):
	fac[i] = (fac[i-1]*i)%mod

gyakugen = [1]*(MAX+1)
gyakugen[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
	gyakugen[i-1] = (gyakugen[i]*i)%mod

def Comb(n,k):#nCk
	return (fac[n]*gyakugen[k]*gyakugen[n-k])%mod

#K=k,N=n,0pair = 0
def calc(k,n,i):
	x = (i-2)//2
	k -= x
	n -= x
	if k == 1:
		if n <= 1:
			return n
		else:
			return 0
	elif n == 0:
		return pow(2,x,mod)
	elif n < 0 or k <= 0:
		return 0

	tmp = 0
	for j in range(2):
		zb = n-j
		zm = k-2
		tmp += Comb(zb+zm,zb)%mod
	tmp %= mod
	tmp *= pow(2,x,mod)
	return tmp

ans = []
for i in range(2,K+2):
	if i%2 == 0:
		pairs = (i-2)//2
		tmp = 0
		for p0 in range(pairs+1):
			tmp += calc(K-p0*2,N,i-p0*2)*Comb(pairs,p0)%mod
			tmp %= mod
	ans.append(tmp)
	print(tmp)

ans = ans[::-1]
for i in range(1,K):
	print(ans[i])