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: Accepted

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

Factorial=[1]*(N+K+1)
for i in range(1,N+K+1):
  Factorial[i]=Factorial[i-1]*(i)%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//2)**2)*x%mod

inverseFactorial=[1]*(N+K+1)
inverseFactorial[N+K]=power(Factorial[N+K],mod-2)
for i in range(0,N+K)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def C(x,y):
  if x<y or y<0:
    return 0
  else:
    return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod
def H(x,y):
  return C(x+y-1,y)

def ans(M,N,K):
  res=0
  for m in range(1,M+1)[::-1]:
    if m%2:
      res+=C(M,m)*H(K,N-2*m)
    else:
      res+=(-1)*C(M,m)*H(K,N-2*m)
  return (H(K,N)-res)%mod
  

for i in range(2,2*K+1):
  if i%2:
    print(ans(min(K,i-1)-i//2,N,K))
  else:
    print((ans(min(K,i-1)-i//2,N-1,K-1)+ans(min(K,i-1)-i//2,N,K-1))%mod)

Submission status: Accepted

Solution code:
K,N=map(int,input().split())
mod=998244353
L=max(K,N)
table=[1]*(3*L+5)
t=1
for i in range(1,3*L+5):
    t*=i
    t%=mod
    table[i]=t
rtable=[1]*(3*L+5)
t=1
for i in range(1,3*L+5):
    t*=pow(i,mod-2,mod)
    t%=mod
    rtable[i]=t
ans=[]
for k in range(2,K+2):
    num=0
    if k%2==1:
        l=k//2
        p=l
        r=K-2*l
        for q in range(l+1):
            if N-q>=0 and r+q-1>=0:
                s=(table[l]*rtable[q]*rtable[l-q])%mod
                s=(s*pow(2,q,mod))%mod
                t=(table[N+r-1]*rtable[N-q]*rtable[r+q-1])%mod
                s=(s*t)%mod
                num+=s
                num=num%mod
                #print(10,q,k,l,p,num,s)
        ans.append(num)
    else:
        l=k//2
        p=l-1
        r=K-k+1
        for q in range(p+1):
            if N-q-1>=0 and r+q-1>=0:
                s=(table[p]*rtable[q]*rtable[p-q])%mod
                s=(s*pow(2,q,mod))%mod
                t=(table[N+r-2]*rtable[N-q-1]*rtable[r+q-1])%mod
                s=(s*t)%mod
                num+=s
                num%=mod
                #print(9,q,k,l,p,num,s)
            if N-q>=0 and r+q-1>=0:
                s=(table[p]*rtable[q]*rtable[p-q])%mod
                s=(s*pow(2,q,mod))%mod
                t=(table[N+r-1]*rtable[N-q]*rtable[r+q-1])%mod
                s=(s*t)%mod
                num+=s
                num%=mod 
                #print(10,q,k,l,p,num,s)
        ans.append(num)
print('\n'.join(map(str,ans)))
ans=ans[::-1]
print('\n'.join(map(str,ans[1:])))

Submission status: Accepted

Solution code:
k,n =map(int,input().split())
mod = 998244353
fact = [1]*(n+k+1)
rfact = [1]*(n+k+1)
for i in range(n+k):
    fact[i+1] = rr = ((i+1) * fact[i]) % mod
    rfact[i+1] = pow(rr, mod-2, mod)
def comb(N, K,mod):
    return fact[N] * rfact[K] * rfact[N-K] % mod
kota = []
for i in range(2,k+2):
  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)*pow(2,q,mod)%mod
      if n - q<0:
        break
      r = k-p*2
      if r <0:
        r = 0
      if n+r-1 < n-q:
        continue
      ans += sen* comb(n+r-1,n-q,mod)%mod
    kota.append(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)*pow(2,q,mod)%mod
      if n - q<0:
        break
      r = k-p*2-1
      if r <0:
        r = 0
      if n+r-1 < n-q:
        continue
      ans += sen* comb(n+r-1,n-q,mod)%mod
    for q in range(p+1):
      sen = comb(p,q,mod)*pow(2,q,mod)%mod
      if n - q-1<0:
        break
      r = k-p*2-1
      if r <0:
        r = 0
      if n+r-2 < n-q-1:
        continue
      ans += sen* comb(n+r-2,n-q-1,mod)%mod
    kota.append(ans%mod)
for i in kota:
  print(i)
for i in range(len(kota)-2,-1,-1):
  print(kota[i])

Submission status: Accepted

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 cmb_f(n, r, mod):
#    print(n, r)
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
#    print(g1[n] * g2[r] * g2[n-r] % mod)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = 10**4
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

def EN(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(k2+1):
        if N < j:
            break
        result = (result + mul(mul(cmb_f(k2, j, mod) , cmb_f(N+k1-1, j+k1-1, mod)) , pow(2, j) % mod))% mod
    if i % 2 == 1:
        return result
    for j in range(k2+1):
        if N-1 < j:
            break
        result = (result + mul(mul(cmb_f(k2, j, mod), cmb_f(N+k1-2, j+k1-1, mod)), pow(2, j) % mod))% mod
    return result

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

Submission status: Accepted

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

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)

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

anss = [0] * (2*K+1)
for i in range(2, K+2):
  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
  anss[i] = ans
  print(ans)

for j in range(K+2, 2*K+1):
  print(anss[2*K - j + 2])

Submission status: Accepted

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

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

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

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


def f(n,k,i):
	if i == 2:
		if n < 0 or (k==1 and n>=2): #例外処理
			return 0
		elif n == 0:
			return 1
		else:
			return (Comb(k-2+n,n)+Comb(k-2+n-1,n-1)) % mod
	else: #i>2
		Sp = i//2-1
		ans = 0
		for p in range(Sp+1):
			ans += g(n,k,i,p)
		return ans % mod

def g(n,k,i,p):
	Sp = i//2-1
	if p == 0:
		return f(n-Sp,k-Sp,2) * pow(2,Sp,mod) % mod
	else: #p>0
		return g(n,k-2*p,i-2*p,0) * Comb(Sp,p)

ans = []
for i in range(2,K+2):
	if i%2 == 0:
		tmp = f(N,K,i)
	ans.append(tmp)
	print(tmp)

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

Submission status: Accepted

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

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

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

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


def f(n,k,i):
	if i == 2:
		if n < 0 or (k==1 and n>=2): #例外処理
			return 0

		if n == 0:
			ans = 1
		else:
			ans = Comb(k-2+n,n) + Comb(k-2+n-1,n-1)
		return ans % mod
	else: #i>2
		Sp = i//2-1
		ans = 0
		for p in range(Sp+1):
			ans += g(n,k,i,p)
		return ans % mod

def g(n,k,i,p):
	Sp = i//2-1
	if p == 0:
		return f(n-Sp,k-Sp,2) * pow(2,Sp,mod) % mod
	else: #p>0
		return g(n,k-2*p,i-2*p,0) * Comb(Sp,p)

ans = []
for i in range(2,K+2):
	if i%2 == 0:
		tmp = f(N,K,i)
	ans.append(tmp)
	print(tmp)

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

Submission status: Accepted

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

        return factorials, invs

    def solve(p):
        """Number of patterns where no pair of p appears when n dices are rolled"""
        if cache[p] > -1:
            return cache[p]

        ret = 0
        fp = factorials[p]
        for q in range(1, min(p, n // 2) + 1):
            tmp1 = (fp * invs[q] % MOD) * invs[p - q] % MOD
            tmp2 = (factorials[k + n - 2 * q - 1] * invs[n - 2 * q] % MOD) * ik % MOD
            if q % 2 == 1:
                ret += tmp1 * tmp2
            else:
                ret -= tmp1 * tmp2
            ret %= MOD

        cache[p] = ret = (all_patterns - ret) % MOD
        return ret

    factorials, invs = get_factorials(k + n)
    ik = invs[k - 1]
    all_patterns = factorials[k + n - 1] * invs[n] * ik % MOD
    cache = [-1] * (k // 2 + 2)

    return solve


MOD = 998244353
k, n = map(int, input().split())
if k == 1:
    print(0)
else:
    solve = prepare(k, n, MOD)
    ans = [solve(i // 2 - max(0, i - k - 1)) for i in range(2, k + 2)]
    print('\n'.join(map(str, ans)))
    print('\n'.join(map(str, ans[-2::-1])))

Submission status: Accepted

Solution code:
k,n = list(map(int,input().split()))
mod = 998244353
fact = [1]*(n+k+1)
rfact = [1]*(n+k+1)
for i in range(1, n+k):
    fact[i] = r = (i * fact[i-1]) % mod
    rfact[i] = pow(r, mod-2, mod)

save = []
for p in range(1,int((k+3)/2)):
    i = 2 * p + 1
    temp = 0
    for t in range(min(p+1,n+1)):
        if k-i+t<0:continue
        res = (fact[p] * rfact[t] * rfact[p-t]) % mod
        res *= (fact[n+k-i] * rfact[k-i+t] * rfact[n-t]) % mod
        res *= pow(2,t,mod)
        temp = (temp+res) % mod
    save.append(temp)
output = []
i = 1
while i<k:
    output.append(save[(i-1)//2])
    i+=1

for x in output+[save[-1]]+output[::-1]:
    print(x)

Submission status: Accepted

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

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

memo = {}
def calc(A):
    if A in memo:
        return memo[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 += V[m] * rfact[M-m] * (fact[p]*rfact[N-m] + fact[p-1]*rfact[N-m-1])*rfact[p-N+m] % MOD

        if 2*M+2-K <= N <= M:
            r += V[N] * rfact[M-N] % MOD
        r *= fact[M]
    else:
        p = K - 2*M + N - 1
        for m in range(max(0, 2*M+1-K), min(N, M)+1):
            r += V[m] * rfact[M-m] * rfact[N-m] * rfact[p-N+m] % MOD
        r *= fact[M] * fact[p]
    r = memo[A] = r % MOD
    return r
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: Accepted

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 h(n, k):
    if n < 0 or k < 0:
        return 0
    return comb(n+k, k)

def calc(A):
    M = A//2
    r = 0
    if A % 2:
        p = K - 2*M + N - 2
        for m in range(M+1):
            if K-2*M-2+m < 0 or N-m < 0:
                continue
            r += pow(2, m, MOD) * comb(M, m) * (h(K-2*M-2+m, N-m) + h(K-2*M-2+m, N-m-1)) % MOD
    else:
        p = K - 2*M + N - 1
        for m in range(M+1):
            if K-2*M-1+m < 0 or N-m < 0:
                continue
            r += pow(2, m, MOD) * comb(M, m) * h(K-2*M-1+m, 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: Accepted

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
    fp, ik = factorials[p], invs[k - 1]
    for q in range(1, min(p, n // 2) + 1):
        # tmp1 = factorials[p + q - 1] * invs[q] * invs[p - 1] % MOD
        tmp1 = (fp * invs[q] % MOD) * invs[p - q] % MOD
        tmp2 = (factorials[k + n - 2 * q - 1] * invs[n - 2 * q] % MOD) * ik % MOD
        if q % 2 == 1:
            ret += tmp1 * tmp2
        else:
            ret -= tmp1 * tmp2
        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
    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)
            ans += all_patterns_even1 - 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: Accepted

Solution code:
mod = 998244353
k, n = list(map(int, input().split()))
C = [ [0 for i in range(n + k + 1)] for j in range(n + k + 1) ]
pw = [0 for i in range(n + k + 1)]

for i in range(0, n + k + 1) :
    C[i][0] = 1
    if i == 0 : pw[i] = 1
    else : pw[i] = (pw[i - 1] << 1) % mod
    for j in range(1, i + 1) :
        C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod

def calc(tot, seg) :
    if tot < 0 : return 0
    return C[tot + seg - 1][tot]

for i in range(2, k + k + 1) :
    ans = su = 0
    if i <= k : su = i - 1
    else : su = k + k - i + 1
    if i & 1 :
        for j in range(0, (su >> 1) + 1) :
            ans = ( ans + calc(n - j, k - su + j) * pw[j] % mod * C[su >> 1][j] ) % mod
    else :
        for j in range(0, (su >> 1) + 1) :
            ans = ( ans + calc(n - j - 1, k - su + j) * pw[j] % mod * C[su >> 1][j] ) % mod
            ans = ( ans + calc(n - j, k - su + j) * pw[j] % mod * C[su >> 1][j] ) % mod
    print(ans)

Submission status: Accepted

Solution code:
N = 4010
p = 998244353
mi2 = [0] * N
inv = [0] * N
fac = [0] * N

def C(x, y):
    return fac[x] * inv[y] * inv[x - y] % p

def Calc(n, a, b):
    ans = 0
    for i in range(min(a, n) + 1):
        if i == b == 0:
            continue
        ans += C(a, i) * mi2[i] * C(n + b - 1, n - i) % p
    return ans % p

mi2[0] = fac[0] = inv[0] = inv[1] = 1
for i in range(1, N):
    mi2[i] = mi2[i - 1] * 2 % p
    fac[i] = fac[i - 1] * i % p
for i in range(2, N):
    inv[i] = inv[p % i] * (p - p // i) % p
for i in range(2, N):
    inv[i] = inv[i - 1] * inv[i] % p

k, n = map(int, input().split())
for i in range(2, 2 * k + 1):
    ans = 0
    cnt = min(k, (i - 1) >> 1) - max(i - k, 1) + 1
    if i & 1:
        ans += Calc(n, cnt, k - cnt * 2)
    else:
        ans += Calc(n, cnt, k - cnt * 2 - 1)
        ans += Calc(n - 1, cnt, k - cnt * 2 - 1)
    print(ans % p)

Submission status: Accepted

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


MOD = 998244353

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

factinv = [1]*4000
for i in range(1,4000):
    factinv[i] = pow(fact[i], MOD-2, MOD)

def ncr(n,r):
    if n < 0 or r < 0 or n-r < 0:
        return 0
    return (fact[n] * factinv[r] * factinv[n-r]) % MOD

def nhr(n,r):
    if n == 0 and r == 0:
        return 1
    return ncr(n+r-1, r)

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)*pow(2, nq, MOD)
            t1 %= MOD
            nr = K-np*2-1
            t2 = nhr(nr+nq,N-nq)
            t2 %= MOD
            Ans = (Ans + t1*t2) % MOD
            # 同じ数の組の数字を1つ含む場合
            t2 = nhr(nr+nq,N-nq-1)
            t2 %= MOD
            Ans = (Ans + t1*t2) % MOD
    else:
        # 奇数の場合 : p組全て互いに異なる数
        for nq in range(np+1):
            t1 = ncr(np,nq)*pow(2, nq, MOD)
            t1 %= MOD
            nr = K-np*2
            t2 = nhr(nr+nq,N-nq)
            t2 %= MOD
            Ans = (Ans + t1*t2) % MOD
    print(Ans%MOD)

Submission status: Accepted

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

MOD = 998244353

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

factinv = [1]*4000
for i in range(1,4000):
    factinv[i] = pow(fact[i], MOD-2, MOD)

def ncr(n,r):
    if n < 0 or r < 0 or n-r < 0:
        return 0
    return (fact[n] * factinv[r] * factinv[n-r]) % MOD

def nhr(n,r):
    if n == 0 and r == 0:
        return 1
    return ncr(n+r-1, r)

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)*pow(2, nq, MOD)
            t1 %= MOD
            t2 = nhr(K-np*2+nq-1,N-nq)
            t2 %= MOD
            Ans = (Ans + t1*t2) % MOD
            # 同じ数の組の数字を1つ含む場合
            t2 = nhr(K-np*2+nq-1,N-nq-1)
            t2 %= MOD
            Ans = (Ans + t1*t2) % MOD
    else:
        # 奇数の場合 : p組全て互いに異なる数
        for nq in range(np+1):
            t1 = ncr(np,nq)*pow(2, nq, MOD)
            t1 %= MOD
            t2 = nhr(K-np*2+nq,N-nq)
            t2 %= MOD
            Ans = (Ans + t1*t2) % MOD
    print(Ans%MOD)

Submission status: Accepted

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):
	#i=2に帰着させる
	pairs = (i-2)//2
	k -= pairs
	n -= pairs

	#色々と例外処理
	if n < 0 or k <= 0:
		return 0
	elif k == 1 and n >= 2:
		return 0

	if n == 0: 	 #球が0個なら1通り
		ans = 1
	else:
		ans = 0
		#i=2の時の数え上げ
		for x in range(2):
			ball = n-x	#球
			box = k-1	#箱
			ans += Comb(box-1+ball,ball)%mod

	ans *= pow(2,pairs,mod)	#0pairの選び方
	return ans % mod

ans = []
for i in range(2,K+2):
	if i%2 == 0:
		pairs = (i-2)//2
		tmp = 0
		for p0 in range(pairs+1): #p0 = 0pairの数
			tmp1 = calc(K-p0*2 , N , i-p0*2) %mod #k-p0*2,i-p0*2で0pairが0組
			tmp2 = Comb(pairs,p0) %mod #0pairの選び方
			tmp += tmp1 * tmp2
			tmp %= mod
	ans.append(tmp)
	print(tmp)

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

Submission status: Accepted

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):
	#i=2に帰着させる
	pairs = (i-2)//2
	k -= pairs
	n -= pairs

	#色々と例外処理
	if n < 0 or k <= 0:
		return 0
	elif k == 1 and n >= 2:
		return 0

	if n == 0: 	 #球が0個なら1通り
		ans = 1
	else:
		ans = 0
		#i=2の時の数え上げ
		for x in range(2):
			ball = n-x	#球
			box = k-1	#箱
			ans += Comb(box-1+ball,ball)%mod

	ans *= pow(2,pairs,mod)	#0pairの選び方
	return ans % mod

ans = []
for i in range(2,K+2):
	if i%2 == 0:
		pairs = (i-2)//2
		tmp = 0
		for p0 in range(pairs+1): #p0 = 0pairの数
			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])

Submission status: Accepted

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]
ANSLIST=[]
for i in range(2,2+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]
    ANSLIST.append(ANS%mod)


for i in ANSLIST:
    print(i)
ANSLIST=ANSLIST[::-1]
for j in ANSLIST[1:]:
    print(j)

Submission status: Accepted

Solution code:
K,N = (int(i) for i in input().split())
mod,ans,kn = 998244353,[],K+N
fn,fk = [1]*kn,[1]*kn
for i in range(kn-1): fn[i+1] = (fn[i]*(i+2))%mod
def power(n,k):
	if k==1: return n
	elif k%2==0: return power((n**2)%mod,k//2)
	else: return (n*power(n,k-1))%mod
def comb(n,k):
	if n==0 or k==0 or n==k: return 1
	else: return (((fn[n-1]*fk[n-k-1])%mod)*fk[k-1])%mod
fk[-1] = power(fn[-1],mod-2)
for i in range(2,kn+1): fk[-i] = (fk[-i+1]*(kn+2-i))%mod
x = comb(kn-1,N)
for i in range(2,K+2):
	num,c,y,p = N-2,1,0,i//2
	while num>-1 and c<=p:
		if c%2: y = (y+comb(p,c)*comb(K+num-1,num))%mod
		else: y = (y-comb(p,c)*comb(K+num-1,num))%mod
		num,c = num-2,c+1
	ans.append((x-y)%mod)
for i in range(2,K+2): print(ans[i-2])
for i in range(K,1,-1): print(ans[i-2])

Submission status: Runtime Error

Solution code:
def solve():
    MOD = 998244353
    maxNK = 2000

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

    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

    def getCombss(n, k, invs, MOD):
        def getCombNs(n, k, invs, MOD):
            combNs = [1] * (n//2+1)
            for x in range(1, n//2+1):
                combNs[x] = (combNs[x-1] * (n-x+1) * invs[x]) % MOD
            return (combNs + combNs[:(n+1)//2][::-1])[:k+1]
        combss = [[] for n in range(n+1)]
        for x in range(n+1):
            combss[x] = getCombNs(x, k, invs, MOD)
            combss[x] += [0] * (k+1-len(combss[x]))
        return combss

    invs = getInvs(2*maxNK, MOD)
    combss = getCombss(2*maxNK, maxNK, invs, MOD)

    def getPows(base, n, MOD):
        pows = [1] * (n+1)
        for x in range(1, n+1):
            pows[x] = (pows[x-1] * base) % MOD
        return pows
    pow2s = getPows(2, N, MOD)

    anss = []
    for i in range(2, 2*K+1):
        ans = 0
        numFree = abs(K+1-i)
        numPair = (K-numFree+1)//2
        if i%2 == 1:
            for x in range(numPair+1):
                ans += combss[numPair][x] * pow2s[x] * combss[N+numFree-1][N-x] % MOD
                ans %= MOD
            anss.append(ans)
        else:
            numPair -= 1
            for x in range(numPair+1):
                ans += combss[numPair][x] * pow2s[x] * combss[N+numFree-1][N-x] % MOD
                ans %= MOD
            for x in range(numPair+1):
                ans += combss[numPair][x] * pow2s[x] * combss[N+numFree-2][N-x-1] % MOD
                ans %= MOD
            anss.append(ans)

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


solve()

Submission status: Runtime Error

Solution code:
mod = 998244353
rng = 4100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
def homo(n,k):
  if n<0 or k<=0:
    return 0
  else:
    return cmb(n+k-1,k-1)
k,n = map(int,input().split())
if k%2 == 0:
  flg = 0
else:
  flg = 1
ans = []
for i in range(3,k+2,2):
  ic = (i-1)//2
  anstmp = 0
  for j in range(ic+1):
    t = homo(n-j,(k-ic*2+j))*cmb(ic,j)*pow(2,j,mod)
    anstmp = (anstmp+t)%mod
  ans.append(anstmp)
  ans.append(anstmp)
if flg:
  anstmp = 0
  for j in range(1,k//2+1):
    t = (homo(n-j,j)*homo(n-j-1,j+1))*cmb(k//2,j)*pow(2,j,mod)
    anstmp = (anstmp+t)%mod
  ans.append(anstmp)
ans2 = ans[:-1]
ans2 = ans2[::-1]
print(*ans,*ans2,sep="\n")

Submission status: Runtime Error

Solution code:
mod = 998244353
rng = 2100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
def homo(n,k):
  if n<0 or k<=0:
    return 0
  else:
    return cmb(n+k-1,k-1)
k,n = map(int,input().split())
if k%2 == 0:
  flg = 0
else:
  flg = 1
ans = []
for i in range(3,k+2,2):
  ic = (i-1)//2
  anstmp = 0
  for j in range(ic+1):
    t = homo(n-j,(k-ic*2+j))*cmb(ic,j)*pow(2,j,mod)
    anstmp = (anstmp+t)%mod
  ans.append(anstmp)
  ans.append(anstmp)
if flg:
  anstmp = 0
  for j in range(1,k//2+1):
    t = (homo(n-j,j)*homo(n-j-1,j+1))*cmb(k//2,j)*pow(2,j,mod)
    anstmp = (anstmp+t)%mod
  ans.append(anstmp)
ans2 = ans[:-1]
ans2 = ans2[::-1]
print(*ans,*ans2,sep="\n")

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 4005;
const int   mod = 998244353;

void add(int &a,int b)  {
    a += b;
    if (a >= mod)
        a -= mod;
}
void sub(int &a,int b)  {
    a -= b;
    if (a <  0)
        a += mod;
}
int mul(int a,int b)    {
    return  1ll * a * b % mod;
}
int Pow(int a,int b)    {
    int ans = 1;
    while (b)   {
        if(b & 1)   ans = mul(ans,a);
        a = mul(a,a);   b >>= 1;
    }
    return  ans;
}
int inv(int a,int p)    {
    return  a == 1 ? 1 : p - 1ll * p * inv(p % a,a) / a;
}

typedef pair<int,int>   ii;

int Fac[N];
int Inv[N];

int Ckn(int n,int k)    {
    if (n < k)  return  0;
    if (k < 0)  return  0;

    return  mul(Fac[n],mul(Inv[k],Inv[n - k]));
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    Fac[0] = Inv[0] = 1;

    for(int i = 1 ; i < N ; ++i)    Fac[i] = mul(Fac[i - 1],i);     Inv[N - 1] = inv(Fac[N - 1],mod);
    for(int i = N - 2 ; i ; --i)    Inv[i] = mul(Inv[i + 1],i + 1);

    int k;  cin >> k;
    int n;  cin >> n;

    for(int i = 2 ; i <= k + k ; ++i)   {
        int cnt = min(k,i - 1) - max(1,i - k) + 1;
        int ans = 0;

        for(int j = 0 ; j <=  cnt / 2 ; ++j) {
            int val = mul(Ckn(cnt / 2,j),Pow(2,j));

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

            if (i & 1)  continue;

            add(ans,mul(Ckn(n - 2 + k - cnt,j + k - cnt - 1),val));
        }
        cout << ans << "\n";
    }
}

Submission status: Runtime Error

Solution code:
def cmb(n,r):
  if n<=0:
    return 0
  elif r<0:
    return 0
  elif r>n:
    return 0
  elif r==0:
    return 1
  elif r==n:
    return 1
  else:
    return A[n]*B[r]*B[n-r]%mod
mod=998244353
A=[1,1]
B=[1,1]
for i in range(2,4005):
  A.append(A[-1]*i%mod)
  B.append(B[-1]*pow(i,mod-2,mod))
k,n=map(int,input().split())
ans=[0]*(2*k+1)
for i in range(2,k+3):#i,i+1(i%2=0,i<k(くらい))で同じとか自明か？？？？？
  if i%2==0:
    i=i+1
    for j in range(min(n+1,i//2+1)):
      ans[i-1]=ans[i-1]+cmb(n+k-i,k-i+j)*cmb(i//2,j)*pow(2,j,mod)
  else:
    for j in range(min(n+1,i//2+1)):
      ans[i]=ans[i]+cmb(n+k-i,k-i+j)*cmb(i//2,j)*pow(2,j,mod)

for i in range(k+2,2*k+1):
  ans[i]=ans[2*k+2-i]
for i in range(2,2*k+1):
  print(ans[i])

Submission status: Runtime Error

Solution code:
K, N = map(int, input().split())
P = 998244353
fa = [1]
for i in range(1, 10000):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, 10000)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]

def C(a, b):
    if not (a >= 0 and 0 <= b <= a): return 0
    return fa[a] * fainv[a-b] * fainv[b] % P

A = []
for i in range(1, K-2):
    s = 0
    for j in range(i+1):
        s += C(N+K-1-2*j, K-1) * C(i, j) * (-1) ** j
        s %= P
    A.append(s)
for a in A:
    print(a)
    print(a)
print(A[-1])
for a in A[::-1][1:]:
    print(a)
    print(a)