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: Wrong Answer

Solution code:
import sys

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


kaizyo = [0]
kaizyo_inv = [0]
tmp = 1
for i in range(1, N+K):
    tmp = (tmp*i) % P
    kaizyo.append(tmp)
    kaizyo_inv.append(pow(tmp, P - 2, P))

def comb(n, r):
    if n < r or r < 0:
        return 0
    elif n == r or r == 0:
        return 1
    else:
        return kaizyo[n] * kaizyo_inv[r] * kaizyo_inv[n - r]


inv_2 = pow(2, P - 2, P)
anss = ''
for i in range(2, 2 * K + 1):
    ans = 0
    n_pair = min((i - 1) // 2, (2 * K - i + 1) // 2)
    out_pair = max(0, K - i + 1, i - K - 1)
    which_use = pow(2, n_pair+1, P)
    for j in range(n_pair + 1):
        if n_pair - j > N:
            continue
        not_use = comb(n_pair, j)
        which_use = (which_use * inv_2) % P
        dice_cnt = comb(N - 1 + out_pair, n_pair - j - 1 + out_pair)
        if i%2==0:
            dice_cnt = (dice_cnt + comb(N - 2 + out_pair, n_pair - j - 1 + out_pair))%P
        tmp = (not_use * which_use) % P
        tmp = (tmp * dice_cnt) % P
        ans = (ans + tmp) % P
    anss += str(ans) + '\n'
print(anss.rstrip())

Submission status: Wrong Answer

Solution code:
import sys

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


def comb(n, r):
    if n < r or r < 0:
        return 0
    nume = 1
    deno = 1
    for i in range(1, r + 1):
        nume = (nume * (n - i + 1)) % P
        deno = (deno * i) % P
    deno_inv = pow(deno, P-2, P)
    return nume * deno_inv


def update_comb(n, new_r, pre_r, pre_comb, P):
    if new_r == 0 or new_r == n:
        return 1
    if pre_comb == None:
        return comb(n, new_r)
    nume = 1
    deno = 1
    if pre_r < new_r:
        for r in range(pre_r + 1, new_r + 1):
            nume = (nume*(n-r+1)) % P
            deno = (deno*r) % P
    elif pre_r > new_r:
        for r in range(new_r + 1, pre_r + 1):
            nume = (nume*r) % P
            deno = (deno*(n-r+1)) % P
    deno_inv = pow(deno, P-2, P)
    return (pre_comb * nume * deno_inv) % P


inv_2 = pow(2, P - 2, P)
anss = ''
for i in range(2, 2 * K + 1):
    ans = 0
    n_pair = min((i - 1) // 2, (2 * K - i + 1) // 2)
    out_pair = max(0, K - i + 1, i - K - 1)
    not_use = None
    which_use = pow(2, n_pair+1, P)
    dice_cnt = None
    div_dice_cnt = pow(N - 1 + out_pair, P - 2, P)
    for j in range(n_pair + 1):
        if n_pair - j > N:
            continue
        not_use = update_comb(n_pair, j, j-1, not_use, P)
        # not_use = comb(n_pair, j)
        which_use = (which_use * inv_2) % P
        # which_use = pow(2, n_pair - j, P)
        dice_cnt = update_comb(N - 1 + out_pair, n_pair -
                               j - 1 + out_pair, n_pair - (j-1) - 1 + out_pair, dice_cnt, P)
        # dice_cnt = comb(N - 1 + out_pair, n_pair - j - 1 + out_pair)
        dice_cnt_ = dice_cnt if i % 2 != 0 else (dice_cnt+dice_cnt *
                                                 div_dice_cnt*(N-1+out_pair-1 - (n_pair - j - 1 + out_pair) + 1)) % P
        tmp = (not_use * which_use) % P
        tmp = (tmp * dice_cnt_) % P
        ans = (ans + tmp) % P
        n_pair = min((i - 1) // 2, (2 * K - i + 1) // 2)
    anss += str(ans) + '\n'
print(anss.rstrip())

Submission status: Wrong Answer

Solution code:
import sys

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


def comb(n, r):
    if n < r or r < 0:
        return 0
    nume = 1
    deno = 1
    for i in range(1, r + 1):
        nume = (nume * (n - i + 1)) % P
        deno = (deno * i) % P
    deno_inv = pow(deno, P-2, P)
    return nume * deno_inv

def update_comb(n, new_r, pre_r, pre_comb, P=None):
    if new_r == 0 or new_r == n:
        return 1
    if pre_comb == None:
        if P is not None:
            return comb(n, new_r) % P
        else:
            return comb(n, new_r)
    nume = 1
    deno = 1
    if pre_r < new_r:
        for r in range(pre_r + 1, new_r + 1):
            nume *= n-r+1
            deno *= r
    elif pre_r > new_r:
        for r in range(new_r + 1, pre_r + 1):
            nume *= r
            deno *= n-r+1
    if P is not None:
        deno_inv = pow(deno, P-2, P)
        return (pre_comb * nume * deno_inv) % P
    else:
        return (pre_comb*nume)//deno_inv

inv_2 = pow(2, P - 2, P)
anss = ''
for i in range(2, 2 * K + 1):
    ans = 0
    n_pair = min((i - 1) // 2, (2 * K - i + 1) // 2)
    out_pair = max(0, K - i + 1, i - K - 1)
    not_use = None
    which_use = pow(2, n_pair+1, P)
    dice_cnt = None
    div_dice_cnt = pow(N - 1 + out_pair, P - 2, P)
    for j in range(n_pair + 1):
        if n_pair - j > N:
            continue
        not_use = update_comb(n_pair, j, j-1, not_use, P)
        # not_use = comb(n_pair, j)
        which_use = which_use * inv_2
        # which_use = pow(2, n_pair - j, P)
        dice_cnt = update_comb(N - 1 + out_pair, n_pair -
                               j - 1 + out_pair, n_pair - (j-1) - 1 + out_pair, dice_cnt, P)
        # dice_cnt = comb(N - 1 + out_pair, n_pair - j - 1 + out_pair)
        dice_cnt_ = dice_cnt if i % 2 != 0 else (dice_cnt+dice_cnt *
            div_dice_cnt*(N-1+out_pair-1 - (n_pair - j - 1 + out_pair) + 1))%P
        tmp = (not_use * which_use) % P
        tmp = (tmp * dice_cnt_) % P
        ans = (ans + tmp) % P
        n_pair = min((i - 1) // 2, (2 * K - i + 1) // 2)
    anss += str(ans) + '\n'
print(anss.rstrip())

Submission status: Wrong Answer

Solution code:
import sys
import time
ts = time.time()

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


def comb(n, r):
    if n < r or r < 0:
        return 0
    nume = 1
    deno = 1
    for i in range(1, r + 1):
        nume = (nume * (n - i + 1)) % P
        deno = (deno * i) % P
    deno_inv = pow(deno, P-2, P)
    return nume*deno_inv


inv_2 = pow(2, P-2, P)
for i in range(2, 2 * K + 1):
    ans = 0
    n_pair = min((i - 1) // 2, (2 * K - i + 1) // 2)
    out_pair = max(0, K - i + 1, i - K - 1)
    not_use = 1
    which_use = 1
    dice_cnt = 1
    for j in range(n_pair + 1):
        # not_use = not_use * ()
        # not_use = comb(n_pair, j)
        # which_use = which_use * inv_2
        which_use = pow(2, n_pair - j, P)
        #dice_cnt = comb(N - 1 + out_pair, n_pair - j - 1 + out_pair)
        # if i % 2 == 0:
        #   dice_cnt = (dice_cnt + comb(N - 1 + out_pair - 1, n_pair - j - 1 + out_pair)) % P
        tmp = (not_use * which_use) % P
        tmp = (tmp * dice_cnt) % P
        ans = (ans + tmp) % P
        n_pair = min((i - 1) // 2, (2 * K - i + 1) // 2)
    print(ans)
print(time.time()-ts)

Submission status: Wrong Answer

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


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    # a*x+y*mod = 1
    return (mod+x % mod) % mod


max_num = 2*10**5+1
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

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

ifact[max_num-1] = inv(fact[max_num-1], mod)

for i in range(2, max_num):
    ifact[max_num-i] = (ifact[max_num-i+1] * (max_num-i+1)) % mod


def comb(x, y):
    return fact[x] * ifact[y] * ifact[x-y] % mod


if k == 1:
    print(0)
    exit()
elif k == 2:
    print(2)
    print(2)
    print(2)
    exit()

for i in range(2, 2*k+1):
    ans = 0
    j = 1
    while i-j > k:
        j += 1
    pair = 0
    mid = 0
    while j <= i-j:
        if j != i-j:
            pair += 1
        else:
            mid += 1
        j += 1
    if pair == 0:
        ans += comb(n-1+k-2, k-2) + comb(n+k-2, k-2)
        ans %= mod
    else:
        if mid == 0:
            for i in range(pair+1):
                if k-2*pair+i == 0:
                    continue
                ans += comb(pair, i) * 2**i * comb(n-i + k-2*pair+i-1, k-2*pair+i-1)
                ans %= mod
        else:
            for i in range(pair+1):
                if k-2*pair-mid+i == 0:
                    continue
                ans += comb(pair, i) * 2**i * comb(n-i-1+k-2*pair-mid+i-1,k-2*pair-mid+i-1)
                ans += comb(pair, i) * 2**i * comb(n-i+k-2*pair-mid+i-1,k-2*pair-mid+i-1)
                ans %= mod
    print(ans)

Submission status: Wrong Answer

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,sep="\n")
print(*ans2,sep="\n")

Submission status: Wrong Answer

Solution code:
def cmb(n,r):
  if n<0:
    return 0
  if n==1:
    return 1
  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)%mod)
k,n=map(int,input().split())
if k==1:
  print(0)
  exit()
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))%mod
  else:
    ans[i]=ans[i-1]
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: Wrong Answer

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)%mod)
k,n=map(int,input().split())
if k==1:
  print(0)
  exit()
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))%mod
  else:
    ans[i]=ans[i-1]
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: Wrong Answer

Solution code:
def cmb(n,r):
  if 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)%mod)
k,n=map(int,input().split())
if k==1:
  print(0)
  exit()
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
    ans[i-1]=sum(cmb(n+k-i,k-i+j)*cmb(i//2,j)*pow(2,j,mod) for j in range(min(n+1,i//2+1)))%mod
  else:
    ans[i]=ans[i-1]
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: Wrong Answer

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())
if k==1:
  print(0)
  exit()
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))%mod
  else:
    ans[i]=ans[i-1]
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: Wrong Answer

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

def modinv(n):
    return pow(n,mod-2,mod)
m=n+k
Fact=[1] #階乗
for i in range(1,m+1):
    Fact.append(Fact[i-1]*i%mod)
Finv=[0]*(m+1) #階乗の逆元
Finv[-1]=modinv(Fact[-1])
for i in range(m-1,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)%mod
def comb(n,r):
    if n<r:
        return 0
    r=min(n-r,r)
    return Fact[n]*Finv[r]*Finv[n-r]%mod
def hcomb(n,r):
    return comb(n+r-1,r)

def solve(x):
    ret=0
    if x%2:
        p=x//2
        for q in range(p+1):
            ret+=pow(2,q,mod)*comb(p,q)*hcomb(k-2*p+q,n-q)
            ret%=mod
    else:
        p=x//2-1
        for q in range(p+1):
            ret+=pow(2,q,mod)*comb(p,q)*(hcomb(k-2*p+q-1,n-q)+hcomb(k-2*p+q-1,n-q-1))
            ret%=mod
    return ret

Ans=[]
for i in range(2,k+2):
    Ans.append(solve(i))
print(*Ans,sep='\n')
print(*reversed(Ans[:k-1]),sep='\n')

Submission status: Wrong Answer

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

def modinv(n):
    return pow(n,mod-2,mod)
m=n+k
Fact=[1] #階乗
for i in range(1,m+1):
    Fact.append(Fact[i-1]*i%mod)
Finv=[0]*(m+1) #階乗の逆元
Finv[-1]=modinv(Fact[-1])
for i in range(m-1,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)%mod
def comb(n,r):
    if n<r:
        return 0
    return Fact[n]*Finv[r]*Finv[n-r]%mod
def hcomb(n,r):
    return comb(n+r-1,r)

def solve(x):
    ret=0
    if x%2:
        p=x//2
        for q in range(p+1):
            ret+=pow(2,q,mod)*comb(p,q)*hcomb(k-2*p+q,n-q)
            ret%=mod
    else:
        p=x//2-1
        for q in range(p+1):
            ret+=pow(2,q,mod)*comb(p,q)*(hcomb(k-2*p+q-1,n-q)+hcomb(k-2*p+q-1,n-q-1))
            ret%=mod
    return ret

Ans=[]
for i in range(2,k+2):
    Ans.append(solve(i))
print(*Ans,sep='\n')
print(*reversed(Ans[:k-1]),sep='\n')

Submission status: Wrong Answer

Solution code:
#102-E
mod=998244353
k,n=map(int,input().split())

def modinv(n):
    return pow(n,mod-2,mod)
m=5000
Fact=[1] #階乗
for i in range(1,m+1):
    Fact.append(Fact[i-1]*i%mod)
Finv=[0]*(m+1) #階乗の逆元
Finv[-1]=modinv(Fact[-1])
for i in range(m-1,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)%mod
def comb(n,r):
    if n<r:
        return 0
    return Fact[n]*Finv[r]*Finv[n-r]%mod
def hcomb(n,r):
    return comb(n+r-1,r)
Pow=[1]*(m+1)
for i in range(m):
    Pow[i+1]=Pow[i]*2%mod
def solve(x):
    ret=0
    if x%2:
        p=x//2
        for q in range(p+1):
            ret+=Pow[q]*comb(p,q)*hcomb(k-2*p+q,n-q)
            ret%=mod
    else:
        p=x//2-1
        for q in range(p+1):
            ret+=Pow[q]*comb(p,q)*(hcomb(k-2*p+q-1,n-q)+hcomb(k-2*p+q-1,n-q-1))
            ret%=mod
    return ret

Ans=[]
for i in range(2,k+2):
    Ans.append(solve(i))
print(*Ans,sep='\n')
print(*reversed(Ans[:-1]),sep='\n')

Submission status: Wrong Answer

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

def modinv(n):
    return pow(n,mod-2,mod)
m=n+k
Fact=[1] #階乗
for i in range(1,m+1):
    Fact.append(Fact[i-1]*i%mod)
Finv=[0]*(m+1) #階乗の逆元
Finv[-1]=modinv(Fact[-1])
for i in range(m-1,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)%mod
def comb(n,r):
    if n<r:
        return 0
    return Fact[n]*Finv[r]*Finv[n-r]%mod
def hcomb(n,r):
    return comb(n+r-1,r)
Pow=[1]*(k+1)
for i in range(k):
    Pow[i+1]=Pow[i]*2%mod
def solve(x):
    ret=0
    if x%2:
        p=x//2
        for q in range(p+1):
            ret+=Pow[q]*comb(p,q)*hcomb(k-2*p+q,n-q)
            ret%=mod
    else:
        p=x//2-1
        for q in range(p+1):
            ret+=Pow[q]*comb(p,q)*(hcomb(k-2*p+q-1,n-q)+hcomb(k-2*p+q-1,n-q-1))
            ret%=mod
    return ret

Ans=[]
for i in range(2,k+2):
    Ans.append(solve(i))
print(*Ans, sep="\n")
print(*reversed(Ans[:-1]),sep="\n")

Submission status: Wrong Answer

Solution code:
k,n=map(int,input().split())
mod=998244353
fra=[1]*(n+k+2)
inv=[1]*(n+k+2)
t=1
for i in range(1,n+k+2):
    t*=i
    t%=mod
    fra[i]=t
t=pow(fra[n+k+1],mod-2,mod)
for i in range(n+k+1,0,-1):
    inv[i]=t
    t*=i
    t%=mod
def comb(n,r):
    if n==0:
        return 1
    if r<0:
        return 0
    if r>n:
        return 0
    return fra[n]*inv[n-r]*inv[r]%mod
ans=[]
for i in range(3,k+3):
    t=comb(n+k-i,k-i)
    if i%2==1:
        for j in range(1,i//2+1):
            if n<j:
                break
            t+=pow(2,j,mod)*comb(i//2,j)*comb(n+k-i,k-i+j)
            t%=mod
    else:
        for j in range(1,i//2+1):
            if n<j:
                break
            t+=comb(i//2-1,j)*pow(2,j,mod)*comb(n+k-i,k-i+j)
            t%=mod
            t+=comb(i//2-1,j-1)*pow(2,j-1,mod)*comb(n+k-i,k-i+j)
            t%=mod
    ans.append(t)
for i in ans+ans[-2::-1]:
    print(i)

Submission status: Wrong Answer

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) % MOD for i in range(n+1)) % MOD

answer = []
for S in range(3,K+3,2):
    x = F((S-1)//2, K - S + 1, N)
    answer.append(x)
    answer.append(x)

if K & 2:
    answer = answer[:-1]
    answer += answer[:-1][::-1]
else:
    answer += answer[:-1][::-1]    

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

Submission status: Wrong Answer

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

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

F = [1] * (K + N + 1)
for i in range(1, K + N + 1):
  F[i] = F[i - 1] * i % MOD
IF = [0] * (K + N + 1)
IF[K + N] = power(F[K + N], MOD - 2)
for i in range(K + N - 1, -1, -1):
  IF[i] = IF[i + 1] * (i + 1) % MOD
T = [1] * (K // 2 + 1)
for i in range(1, K // 2 + 1):
  T[i] = T[i - 1] * 2 % MOD

for i in range(2, 2 * K + 1):
  if i <= K:
    x = (i - 1) // 2
  else:
    x = (2 * K - i + 1) // 2
  y = K - 2 * x - 1
  Ans = 0
  if i % 2 == 1:
    for j in range(x + 1):
      if j == 0: k = 1
      else: k = F[x] * IF[j] % MOD
      t = F[N + y] * IF[y + j] * IF[N - j] % MOD
      Ans += T[j] * t * k % MOD
  else:
    for j in range(x + 1):
      if j > N:
        break
      if j == 0: k = 1
      else: k = F[x] * IF[j] % MOD
      t = F[N + y - 1] * IF[y + j - 1] * IF[N - j] % MOD
      Ans += T[j] * t * k % MOD
      t = F[N + y - 2] * IF[y + j - 1] * IF[N - j - 1] % MOD
      Ans += T[j] * t * k % MOD
  print(Ans)

Submission status: Wrong Answer

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

F = [1] * (K + N + 1)
for i in range(1, N + K + 1):
  F[i] = F[i - 1] * i
T = [1] * (K // 2 + 1)
for i in range(1, K // 2 + 1):
  T[i] = T[i - 1] * 2 % MOD

for i in range(2, 2 * K + 1):
  if i <= K:
    x = (i - 1) // 2
  else:
    x = (2 * K - i + 1) // 2
  y = K - 2 * x - 1
  Ans = 0
  if i % 2 == 1:
    for j in range(x + 1):
      if j == 0: k = 1
      else: k = F[x] // F[j]
      t = F[N + y] // (F[y + j] * F[N - j])
      Ans += T[j] * t * k
  else:
    for j in range(x + 1):
      if j == 0: k = 1
      else: k = F[x] // F[j]
      t = F[N + y - 1] // (F[y + j - 1] * F[N - j])
      Ans += T[j] * t * k
      t = F[N + y - 2] // (F[y + j - 1] * F[N - j - 1])
      Ans += T[j] * t * k
  print(Ans % MOD)

Submission status: Wrong Answer

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

M = 998244353
fact = None
factr = None

def comb(n, k):
    if n <= 0 or k < 0:
        return 0
    r = fact[n] * factr[k] % M
    r *= factr[n - k]
    r %= M
    return r


def solve(k, n):
    global fact, factr

    inv = [1] * (k + n + 1)
    for i in range(2, k + n + 1):
        inv[i] = inv[M % i] * (M - M // i) % M
    fact = [1] * (k + n + 1)
    factr = [1] * (k + n + 1)
    for i in range(2, k + n + 1):
        fact[i] = fact[i - 1] * i % M
        factr[i] = factr[i - 1] * inv[i] % M

    if k == 1:
        print(0)
        return

    g0 = (comb(k + n - 2, k - 2) + comb(k + n - 3, k - 2)) % M
    g1 = comb(k + n - 1, k - 1)

    rs0 = [0] * (min(k // 2, n // 2) + 1)
    rs1 = [0] * (min(k // 2, n // 2) + 1)
    for t in range(1, min(k // 2, n // 2) + 1):
        rs0[t] = (comb(k + n - 2 * t - 2, k - 2) + comb(k + n - 2 * t - 3, k - 2)) % M
        rs1[t] = comb(k + n - 2 * t - 1, k - 1)

    results = [0] * (k + 2)

    for i in range(2, k + 2):
        ns = (i - 1) // 2
        ans = g0 if i % 2 == 0 else g1
        p = -1
        for t in range(1, min(ns, n // 2) + 1):
            r = rs0[t] if i % 2 == 0 else rs1[t]
            r *= comb(ns, t)
            r %= M
            ans += M + p * r
            ans %= M
            p = 0 - p
        print(ans)
        results[i] = ans
    for i in range(k + 2, 2 * k + 1):
        print(results[2 * k + 2 - i])


def main():
    k, n = input().split()
    k = int(k)
    n = int(n)

    solve(k, n)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

M = 998244353
fact = None
factr = None

def comb(n, k):
    if n <= 0 or k < 0:
        return 0
    r = fact[n] * factr[k] % M
    r *= factr[n - k]
    r %= M
    return r


def solve(k, n):
    global fact, factr

    inv = [1] * (k + n + 1)
    for i in range(2, k + n + 1):
        inv[i] = inv[M % i] * (M - M // i) % M
    fact = [1] * (k + n + 1)
    factr = [1] * (k + n + 1)
    for i in range(2, k + n + 1):
        fact[i] = fact[i - 1] * i % M
        factr[i] = factr[i - 1] * inv[i] % M

    if k == 1:
        print(0)
        return

    g0 = (comb(k + n - 2, k - 2) + comb(k + n - 3, k - 2)) % M
    g1 = comb(k + n - 1, k - 1)

    rs0 = [0] * (min(k // 2, n // 2) + 1)
    rs1 = [0] * (min(k // 2, n // 2) + 1)
    for t in range(1, min(k // 2, n // 2) + 1):
        rs0[t] = (comb(k + n - 2 * t - 2, k - 2) + comb(k + n - 2 * t - 3, k - 2)) % M
        rs1[t] = comb(k + n - 2 * t - 1, k - 1)

    for i in range(2, 2 * k + 1):
        ns = (i - 1) // 2 - max(1, i - k) + 1
        ans = g0 if i % 2 == 0 else g1
        p = -1
        for t in range(1, min(ns, n // 2) + 1):
            r = rs0[t] if i % 2 == 0 else rs1[t]
            r *= comb(ns, t)
            r %= M
            ans += M + p * r
            ans %= M
            p = 0 - p
        print(ans)


def main():
    k, n = input().split()
    k = int(k)
    n = int(n)

    solve(k, n)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

M = 998244353
fact = None
factr = None

def comb(n, k):
    if n < 0 or k < 0:
        return 0
    r = fact[n] * factr[k] % M
    r *= factr[n - k]
    r %= M
    return r


def solve(k, n):
    global fact, factr

    inv = [1] * (k + n + 1)
    for i in range(2, k + n + 1):
        inv[i] = inv[M % i] * (M - M // i) % M
    fact = [1] * (k + n + 1)
    factr = [1] * (k + n + 1)
    for i in range(2, k + n + 1):
        fact[i] = fact[i - 1] * i % M
        factr[i] = factr[i - 1] * inv[i] % M

    if k == 1:
        print(0)
        return

    g0 = (comb(k + n - 2, k - 2) + comb(k + n - 3, k - 2)) % M
    g1 = comb(k + n - 1, k - 1)

    for i in range(2, 2 * k + 1):
        ns = (i - 1) // 2 - max(1, i - k) + 1
        ans = g0 if i % 2 == 0 else g1
        p = -1
        for t in range(1, min(ns, n // 2) + 1):
            if i % 2 == 0:
                r = (comb(k + n - 2 * t - 2, k - 2) + comb(k + n - 2 * t - 3, k - 2)) % M
                r *= comb(ns, t)
                r %= M
            else:
                r = comb(k + n - 2 * t - 1, k - 1) * comb(ns, t) % M
            ans += M + p * r
            ans %= M
            p = 0 - p
        print(ans)


def main():
    k, n = input().split()
    k = int(k)
    n = int(n)

    solve(k, n)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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
fact = [1]*(n+k+1)
rfact = [1]*(n+k+1)
for i in range(n+k):
    fact[i+1] = r = ((i+1) * fact[i]) % mod
    rfact[i+1] = pow(r, mod-2, mod)
 
def comb(n, k,MOD):
    return fact[n] * rfact[k] * rfact[n-k] % MOD
com = [[None] *4050 for i in range(4050)]
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
      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
      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
      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: Wrong Answer

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(1)
else:
    result = []
    for i in range(K):
        result.append(str(EE(i+2)))
    print("\n".join(result + result[:-1][::-1]))

Submission status: Wrong Answer

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(p+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: Wrong Answer

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(p+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 = save+[save[-1]]+save[::-1]
for x in output:
    print(x)

Submission status: Wrong Answer

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