2..3...4.... Wonderful! Wonderful! (Codeforces 1930E)
Tags: Math, combinatorics

Stack has an array $$$a$$$ of length $$$n$$$ such that $$$a_i = i$$$ for all $$$i$$$ ($$$1 \leq i \leq n$$$). He will select a positive integer $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor$$$) and do the following operation on $$$a$$$ any number (possibly $$$0$$$) of times.  Select a subsequence$$$^\dagger$$$ $$$s$$$ of length $$$2 \cdot k + 1$$$ from $$$a$$$. Now, he will delete the first $$$k$$$ elements of $$$s$$$ from $$$a$$$. To keep things perfectly balanced (as all things should be), he will also delete the last $$$k$$$ elements of $$$s$$$ from $$$a$$$. Stack wonders how many arrays $$$a$$$ can he end up with for each $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor$$$). As Stack is weak at counting problems, he needs your help. Since the number of arrays might be too large, please print it modulo $$$998\,244\,353$$$.$$$^\dagger$$$ A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deleting several (possibly, zero or all) elements. For example, $$$[1, 3]$$$, $$$[1, 2, 3]$$$ and $$$[2, 3]$$$ are subsequences of $$$[1, 2, 3]$$$. On the other hand, $$$[3, 1]$$$ and $$$[2, 1, 3]$$$ are not subsequences of $$$[1, 2, 3]$$$.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^3$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$3 \leq n \leq 10^6$$$) — the length of the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test, on a new line, print $$$\lfloor \frac{n-1}{2} \rfloor$$$ space-separated integers — the $$$i$$$-th integer representing the number of arrays modulo $$$998\,244\,353$$$ that Stack can get if he selects $$$k=i$$$.

Note: In the first test case, two $$$a$$$ are possible for $$$k=1$$$:   $$$[1,2,3]$$$;  $$$[2]$$$. In the second test case, four $$$a$$$ are possible for $$$k=1$$$:   $$$[1,2,3,4]$$$;  $$$[1,3]$$$;  $$$[2,3]$$$;  $$$[2,4]$$$. In the third test case, two $$$a$$$ are possible for $$$k=2$$$:   $$$[1,2,3,4,5]$$$;  $$$[3]$$$. 

Sample Inputs:
4
3
4
5
10

Sample Outputs:
2 
4 
10 2 
487 162 85 10

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def comb(n, r):
    return fact[n] * inv[r] % mod * inv[n - r] % mod if n >= r >= 0 else 0
t = int(input())
ans = []
mod = 998244353
l = 2 * pow(10, 6) + 5
fact = [1] * (l + 1)
for i in range(1, l + 1):
    fact[i] = i * fact[i - 1] % mod
inv = [1] * (l + 1)
inv[l] = pow(fact[l], mod - 2, mod)
for i in range(l - 1, -1, -1):
    inv[i] = (i + 1) * inv[i + 1] % mod
for _ in range(t):
    n = int(input())
    ans0 = []
    for k in range(1, (n - 1) // 2 + 1):
        ans1 = 1
        u = 0
        while u + 2 * k <= n:
            u += 2 * k
            v = u - (k - 1) * 2
            ans1 += comb(n, u) - comb(n - v + 1, 2 * k - 1)
        ans0.append(ans1 % mod)
    ans.append(' '.join(map(str, ans0)))
sys.stdout.write('\n'.join(ans))

Solution (Python):
import sys
input = sys.stdin.readline
MOD = 998244353
N = 10 ** 6 + 5
fact = [1] * N
inv = [1] * N
fact_inv = [1] * N
for i in range(2, N):
    fact[i] = i * fact[i - 1] % MOD
    inv[i] = -(MOD // i) * inv[MOD % i] % MOD
    fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD

def binomial_mod(n, k, m):
    if k < 0 or k > n:
        return 0
    return fact[n] * fact_inv[k] % m * fact_inv[n - k] % m

def solve():
    n = int(input())
    res = []
    for k in range(1, (n - 1) // 2 + 1):
        ans = 1
        for i in range(1, (n - 1) // (2 * k) + 1):
            m = n - 2 * k * i
            ans += binomial_mod(n, m, MOD)
            ans -= binomial_mod(m + 2 * k - 1, 2 * k - 1, MOD)
        res.append(ans % MOD)
    return ' '.join(map(str, res))
T = int(input())
out = [solve() for _ in range(T)]
print('\n'.join(map(str, out)))

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]
mod = 998244353
table_size = 10 ** 6 + 10
fac = [1] * (table_size + 1)
finv = [1] * (table_size + 1)
for i in range(2, table_size + 1):
    fac[i] = fac[i - 1] * i % mod
finv[table_size] = pow(fac[table_size], mod - 2, mod)
for i in range(table_size - 1, -1, -1):
    finv[i] = finv[i + 1] * (i + 1) % mod

def rebuild(n):
    global table_size, fac, finv
    fac += [0] * (n - table_size)
    fac += [0] * (n - table_size)
    finv += [0] * (n - table_size)
    for i in range(table_size + 1, n + 1):
        fac[i] = fac[i - 1] * i % mod
    finv[n] = inv(fac[n])
    for i in range(n - 1, table_size, -1):
        finv[i] = finv[i + 1] * (i + 1) % mod
    table_size = n

def binom(n, k):
    if n < 0 or k < 0:
        return 0
    if k > n:
        return 0
    if n > table_size:
        rebuild(n + 10 ** 4)
    return fac[n] * finv[k] % mod * finv[n - k] % mod

def fpow(x, k):
    res = 1
    while k:
        if k & 1:
            res = res * x % mod
        x = x * x % mod
        k >>= 1
    return res

def inv(a):
    if a < table_size:
        return fac[a - 1] * finv[a] % mod
    return fpow(a, mod - 2)

def solve():
    n = int(input())
    ans = []
    for k in range(1, (n - 1) // 2 + 1):
        c = 1
        tmp = 1
        while 2 * k * c + 1 <= n:
            tmp += binom(n, 2 * k * c)
            A = binom(n - (2 * k * (c - 1) + 2) + 1, 2 * k - 1)
            tmp -= A
            tmp %= mod
            c += 1
        ans.append(tmp % mod)
    print(*ans)
for _ in range(int(input())):
    solve()