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:
#!/usr/bin/env python

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

sys.setrecursionlimit(10000000)

m = [[-1] * 2001 for i in range(4001)]

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

    def comb(n, k):
        if n < 0 or k < 0:
            return 0
        if n == k or k == 0:
            return 1
        if m[n][k] < 0:
            m[n][k] = (comb(n - 1, k) + comb(n - 1, k - 1)) % MOD
        return m[n][k]

    m2 = {}
    def p2(n):
        if n == 0:
            return 1
        if not n in m2:
            m2[n] = (p2(n - 1) * 2) % MOD
        return m2[n]

    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 += comb(N + K - 2 - rem * 2, K - 2 - rem * 2 + j) \
                * comb(rem, j) * p2(j)
                ans += comb(N + K - 3 - rem * 2, K - 2 - rem * 2 + j) \
                * comb(rem, j) * p2(j)
                ans %= MOD
        else:
            rem = i / 2
            for j in range(rem + 1):
                ans += comb(N + K - 1 - rem * 2, K - 1 - rem * 2 + j) \
                * comb(rem, j) * p2(j)
                ans %= MOD
        ls.append(ans % MOD)

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

    for num in ls:
        print num

f()

Submission status: Accepted

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:
            which_use = (which_use * inv_2) % P
            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: Accepted

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

max_n = 5000
fac, finv, inv = [0]*max_n, [0]*max_n, [0]*max_n

def comInit(max_n):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

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

comInit(max_n)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

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

ans = []
for j in range(2,k+2):
    tmp = 0
    x = (j-1)//2
    for i in range(j//2 + 1):
        comb1 = com(n+k-j,n-i)
        comb2 = (com(x,i) * ex2[i])%mod
        if(j%2==0):
            comb1 += com(n+k-j-1,n-i-1)
            comb1 %= mod
        tmp += comb1*comb2
        tmp %= mod

    ans.append(tmp)

ans2 = ans[:-1]
ans += ans2[::-1]
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
mod=998244353

def cmb(n,r):
  if r<0 or r>n:
    return 0
  return (g1[n]*g2[r]*g2[n-r])%mod

g1=[1,1]
g2=[1,1]
inv=[0,1]
for i in range(2,100003):
  g1.append((g1[-1]*i)%mod)
  inv.append((-inv[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inv[-1])%mod)
K,N=map(int,input().split())
C=[0]*(2*K)
for i in range(K):
  for j in range(i+1,K):
    C[i+j]+=1
for i in range(2*K-1):
  P=0
  if i&1:
    for j in range(C[i]+1):
      P=(P+cmb(K+N-2*C[i]-1,N-j)*pow(2,j,mod)*cmb(C[i],j))%mod
  else:
    for k in range(2):
      for j in range(C[i]+1):
        P=(P+cmb(K+N-2*C[i]-2-k,N-j-k)*pow(2,j,mod)*cmb(C[i],j))%mod
  print(P)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] % md * ifac[com_n - com_r] % md

def nHr(hn,hr):
    return nCr(hn+hr-1,hr)

md = 998244353
n_max = 5000
fac = [1]
for i in range(1, n_max + 1): fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1) % md

def solve():
    res=0
    for p in range(min(t,n)//2+1):
        cur=nCr(t//2,p)*nHr(k,n-2*p)
        if p&1:res-=cur
        else:res+=cur
        res%=md
    return res

k,n=MI()
ans=[]
for t in range(2,k+2):
    a=solve()
    ans.append(a)
    print(a)
ans.reverse()
for a in ans[1:]:print(a)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n = 6000

fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod

def h(n, r):
    return comb(n + r - 1, r - 1)

k, n = LI()
for i in range(2, 2 * k + 1):
    ret = 0
    m = min(i // 2, (k - (i + 1) // 2 + 1))
    if i % 2:
        for j in range(m + 1):
            ret += comb(m, j) * pow(2, j, mod) * h(n - j, k - m * 2 + j)
    else:
        for j in range(m + 1):
            if j:
                ret += comb(m - 1, j - 1) * pow(2, j - 1, mod) * h(n - j, k - m * 2 + j)
                ret += comb(m - 1, j) * pow(2, j, mod) * h(n - j, k - m * 2 + 1 + j)
            else:
                ret += comb(m, j) * pow(2, j, mod) * h(n - j, k - m * 2 + 1 + j)
    print(ret % mod)

Submission status: Accepted

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

mod = 998244353


def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 10**5 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


K, N = map(int, input().split())
for i in range(2, 2*K+1):
    if i%2 == 1:
        p = min(i//2, (2*K-i+1)//2)
        ans = 0
        t = 1
        for c in range(min(N,p)+1):
            ans = (ans + cmb(K+N-2*p-1, N-c) * cmb(p, c) * t) % mod
            t = t * 2 % mod
        print(ans)
    else:
        p = min(i//2-1, (2*K-i)//2)
        ans = 0
        t = 1
        for c in range(min(N,p)+1):
            ans = (ans + (cmb(K+N-2*p-3, N-c-1) + cmb(K+N-2*p-2, N-c)) * cmb(p, c) * t) % mod
            t = t * 2 % mod
        print(ans)

Submission status: Accepted

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, K+2, 2):
        ans = 0
        numFree = abs(K+1-i)
        numPair = (K-numFree+1)//2
        numPair -= 1
        for x in range(min(numPair, N)+1):
            ans += combss[numPair][x] * pow2s[x] * combss[N+numFree-1][N-x] % MOD
            ans %= MOD
        for x in range(min(numPair, N)+1):
            ans += combss[numPair][x] * pow2s[x] * combss[N+numFree-2][N-x-1] % MOD
            ans %= MOD
        anss.append(ans)
        if i+1 <= K+1:
            anss.append(ans)

    anss = anss + anss[:-1][::-1]
    print('\n'.join(map(str, anss)))


solve()

Submission status: Accepted

Solution code:
mod = 998244353
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    # comb init
    nmax = 6 * 10 ** 3 + 10  # change here
    fac = [0] * nmax
    finv = [0] * nmax
    inv = [0] * nmax
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, nmax):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod

    def comb(n, r):
        if n < r:
            return 0
        else:
            return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod

    K, N = map(int, input().split())
    for i in range(2, 2*K+1):
        if i & 1:
            A = 0
            B = 0
            for j in range(1, K+1):
                if 1 <= i - j <= K:
                    A += 1
                else:
                    B += 1
            A //= 2
            ans = 0
            for a in range(A+1):
                if B == 0 and a == A:
                    break
                ans = (ans + (-1)**(a&1) * ((comb(N + (A+B-a) - 1, N) * pow(2, A-a, mod))%mod * comb(A, a))%mod)%mod
            print(ans)
        else:
            A = 0
            B = 0
            for j in range(1, K + 1):
                if 1 <= i - j <= K:
                    A += 1
                else:
                    B += 1
            A = (A-1) // 2
            ans = 0
            for a in range(A + 1):
                if B == 0 and a == A:
                    break
                ans = (ans + (-1) ** (a & 1) * (
                            (comb(N + (A + B - a) - 1, N) * pow(2, A - a, mod)) % mod * comb(A, a)) % mod) % mod
            for a in range(A + 1):
                if B == 0 and a == A:
                    break
                ans = (ans + (-1) ** (a & 1) * (
                            (comb(N-1 + (A + B - a) - 1, N-1) * pow(2, A - a, mod)) % mod * comb(A, a)) % mod) % mod
            print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc102/tasks/arc102_c

各Kに関して O(N)くらいで求める必要がある
とあるkについて考えてみようか

kが奇数の時を考える。

1,k-1
2,k-2
3,k-3
…

の各ペアに関して片方のみ登場していい。
登場して良い数字の選び方は2^(k/2)通り
登場していいのに出ないやつがいると、重複する
包除原理で消すか？ t(=k/2)ペアあるとする。いつ出ても構わないのがx個あったとする

{2^t * H(n,x+t) } - tC1 * {2^(t-1) * H(n,x+t-1) } + tC2 * {}　…
で求まる。 計算量はO(K)くらい

kが偶数の時は,k/2が1度だけ登場する or しないを選んでおく
登場すると決めたら,nが1だけ小さくなる　後は同様にやるだけ

tの数、k/2 じゃないじゃん
→これを考え直さなきゃ k > Kのとき上手く計算できない
l,rで考えよう→ rが最大はK なのでl最小は k-K
k-K-1をKから引くと K-(k-K-1) = 2*K-k+1 の長さ
ここから両端からとっていくので　t = (2*K-k)//2となる


"""

#modのn!と、n!の逆元を格納したリストを返す(拾いもの)
#factorialsには[1, 1!%mod , 2!%mod , 6!%mod… , n!%mod] が入っている
#invsには↑の逆元が入っている

def modfac(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 modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)
    return fac[n] * inv[n-r] * inv[r] % mod

def modnHr(n,r,mod,fac,inv):
    return modnCr(n+r-1,n,mod,fac,inv)

K,N = map(int,input().split())
mod = 998244353
fac,inv = modfac(N+K+10,mod)

for k in range(2,2*K+1):

    ans = 0

    if k % 2 == 1: #奇数の時
        if k <= K:
            t = k // 2
        else:
            t = (2*K-k+1)//2
        x = K - t*2

        if x == 0:
            end = t
        else:
            end = t+1

        for u in range(0,end):
            now = modnCr(t,u,mod,fac,inv) * pow(2,t-u,mod) * modnHr(N,x+t-u,mod,fac,inv)
            if u % 2 == 0:
                ans += now
            else:
                ans -= now
            ans %= mod
            #print (u,now)

    else: #偶数の時

        if k <= K:
            t = (k-1) // 2
        else:
            t = (2*K-k)//2
 
        x = K - t*2 - 1

        if x == 0:
            end = t
        else:
            end = t+1

        for u in range(0,end):
            now = modnCr(t,u,mod,fac,inv) * pow(2,t-u,mod) * ( modnHr(N,x+t-u,mod,fac,inv) + modnHr(N-1,x+t-u,mod,fac,inv) )
            if u % 2 == 0:
                ans += now
            else:
                ans -= now
            ans %= mod
            #print (u,now)

    
    print (ans % mod)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
mod = 998244353
def inved(a):
  x, y, u, v, k, l = 1, 0, 0, 1, a, mod
  while l != 0:
    x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
    k, l = l, k % l
  return x % mod

X = [0 for i in range(2*K-1)]
frac = [1]
for i in range(N + K):
  frac.append(((i+1)*frac[i])%mod)
invf = []
for i in range(N + K + 1):
  invf.append(inved(frac[i]))
for k in range(2, K+2):
  S = 0
  sign = 1
  l = k // 2
  for m in range(min(l+1, N//2+1)):
    prod = (sign * (frac[l]*frac[N+K-2*m-1])) % mod
    prod *= (invf[m]*invf[l-m]) % mod
    prod %= mod
    prod *= (invf[N-2*m] * invf[K-1]) % mod
    prod %= mod
    S += prod
    S %= mod
    sign *= -1
  X[k-2], X[2*K-k] = S, S
for i in range(2*K-1):
  print(X[i])

Submission status: Accepted

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):
    if x < 0 or y < 0 or x < y:
        return 0
    else:
        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()

ansl = [0]*(2*k-1)

for ii in range(2, 2*k+1):
    ans = 0
    j = max(1,ii-k)

    if i % 2 == 0:
        pair = ii//2 - j
        mid = 1
    else:
        pair = (ii+1)//2 - j
        mid = 0

    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
    ansl[ii-2] = ans
    if ii == k+1:
        break


for i in range(k-1):
    print(ansl[i])

print(ansl[k-1])

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

Submission status: Accepted

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

Solution code:
def cmb(n,r):
  if n<0:
    return 0
  if n==0:
    if r!=0:
      return 0
    else:
      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: Accepted

Solution code:
K, N = map(int, input().split())
mod = 998244353
A = []
p = mod - 2
while p != 0:
  A = [p%2] + A[:]
  p //= 2
def inved(x):
  y = 1
  for _ in range(len(A)):
    if A[_] == 1:
      y *= x
      y %= mod
    if _ != len(A) - 1:
      y *= y
      y %= mod
  return y

X = [0 for i in range(2*K-1)]
frac = [1]
for i in range(N + K):
  frac.append(((i+1)*frac[i])%mod)
invf = []
for i in range(N + K + 1):
  invf.append(inved(frac[i]))
for k in range(2, K+2):
  S = 0
  sign = 1
  l = k // 2
  for m in range(min(l+1, N//2+1)):
    prod = (sign * (frac[l]*frac[N+K-2*m-1])) % mod
    prod *= (invf[m]*invf[l-m]) % mod
    prod %= mod
    prod *= (invf[N-2*m] * invf[K-1]) % mod
    prod %= mod
    S += prod
    S %= mod
    sign *= -1
  X[k-2], X[2*K-k] = S, S
for i in range(2*K-1):
  print(X[i])

Submission status: Accepted

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+1)//2+1):
    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 i in range(2*K-1):
    print(A[min(i//2, (2*K-i-2)//2)])

Submission status: Accepted

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 r<0 or 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[:k-1]),sep='\n')

Submission status: Accepted

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 & 1:
    answer = answer[:-1]
    answer += answer[:-1][::-1]
else:
    answer += answer[:-1][::-1]    

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

Submission status: Accepted

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

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
fraci = [None]*5010
for i in range(5010):
    fraci[i] = pow(frac[i], mod-2, mod)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%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: Accepted

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

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

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

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv
mod = 998244353
K, N = map(int, input().split())
comb = Combination(10000, mod=mod)
def C(n, r):
    if n<r or r<0:
        return 0
    else:
        return comb(n, r)
def H(n, r):
    return C(n+r-1, r)
L = []
for i in range(2, 2*K+1, 2):
    ans = 0
    M = i//2
    b = 1
    for j, a in enumerate(range(M, K)):
        if M-j<0:
            break
        ans += pow(2, M-j, mod) * C(M, j) * H(K-a, N) * b
        #print((j, a), C(M, j) , H(N, K-a), b, pow(2, M-j, mod) * C(M, j) * H(K-a, N) * b)
        ans %= mod
        b = -b
    print(ans)
    if i == K+1:
        break
    elif i == K:
        print(ans)
        print(ans)
        break
    L.append(ans)
    print(ans)
    L.append(ans)

print(*L[::-1], sep="\n")

Submission status: Accepted

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_i = ans[-1]
            break
            # 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: Accepted

Solution code:
# Acknowledge: https://atcoder.jp/contests/arc102/submissions/3127544
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

memo = []
for p in range(1, (k+3)//2):
    i = 2*p+1
    tmp = 0
    for t in range(min(p+1, n+1)):
        if k-i+t < 0:
            continue
        res = nCk(p, t)
        res *= nCk(n+k-i, k-i+t)
        res *= pow(2, t, MOD)
        tmp = (tmp+res)%MOD
    memo.append(tmp)

ans = []
for i in range(1, k):
    ans.append(memo[(i-1)//2])
for a in ans+[memo[-1]]+ans[::-1]:
    print(a)

Submission status: Accepted

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

M = 998244353
fact = None
factr = None

def comb(n, k):
    if n <= 0 or k < 0 or n < k:
        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
    if k == 2:
        for _ in range(3):
            print(2)
        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: Accepted

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) * 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) * pow(2, j, MOD) * comb(n+k-i, k-i+j)
			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")