Wooden Spoon (Codeforces 1785D)
Tags: Math, fft

$$$2^n$$$ people, numbered with distinct integers from $$$1$$$ to $$$2^n$$$, are playing in a single elimination tournament. The bracket of the tournament is a full binary tree of height $$$n$$$ with $$$2^n$$$ leaves.When two players meet each other in a match, a player with the smaller number always wins. The winner of the tournament is the player who wins all $$$n$$$ their matches.A virtual consolation prize "Wooden Spoon" is awarded to a player who satisfies the following $$$n$$$ conditions:   they lost their first match;  the player who beat them lost their second match;  the player who beat that player lost their third match;  $$$\ldots$$$;  the player who beat the player from the previous condition lost the final match of the tournament. It can be shown that there is always exactly one player who satisfies these conditions.Consider all possible $$$(2^n)!$$$ arrangements of players into the tournament bracket. For each player, find the number of these arrangements in which they will be awarded the "Wooden Spoon", and print these numbers modulo $$$998\,244\,353$$$.

Input: The only line contains a single integer $$$n$$$ ($$$1 \le n \le 20$$$) — the size of the tournament.There are $$$20$$$ tests in the problem: in the first test, $$$n = 1$$$; in the second test, $$$n = 2$$$; $$$\ldots$$$; in the $$$20$$$-th test, $$$n = 20$$$.

Output: Print $$$2^n$$$ integers — the number of arrangements in which the "Wooden Spoon" is awarded to players $$$1, 2, \ldots, 2^n$$$, modulo $$$998\,244\,353$$$.

Note: In the first example, the "Wooden Spoon" is always awarded to player $$$2$$$.In the second example, there are $$$8$$$ arrangements where players $$$1$$$ and $$$4$$$ meet each other in the first match, and in these cases, the "Wooden Spoon" is awarded to player $$$3$$$. In the remaining $$$16$$$ arrangements, the "Wooden Spoon" is awarded to player $$$4$$$.

Sample Inputs:
1

2

3

Sample Outputs:
0
2

0
0
8
16

0
0
0
1536
4224
7680
11520
15360

Solution (Python):
import re
import functools
import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce, cmp_to_key
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heappushpop, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
from typing import *
from operator import add, xor, mul, ior, iand, itemgetter
import bisect
from string import ascii_lowercase, ascii_uppercase
BUFSIZE = 4096
inf = float('inf')
if 'PyPy' in sys.version:
    import pypyjit
    pypyjit.set_param('max_unroll_recursion=-1')

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

class Factorial:

    def __init__(self, N, mod) -> None:
        self.mod = mod
        self.f = [1 for _ in range(N)]
        self.g = [1 for _ in range(N)]
        for i in range(1, N):
            self.f[i] = self.f[i - 1] * i % self.mod
        self.g[-1] = pow(self.f[-1], mod - 2, mod)
        for i in range(N - 2, -1, -1):
            self.g[i] = self.g[i + 1] * (i + 1) % self.mod

    def fac(self, n):
        return self.f[n]

    def fac_inv(self, n):
        return self.g[n]

    def comb(self, n, m):
        if n < m:
            return 0
        return self.f[n] * self.g[m] % self.mod * self.g[n - m] % self.mod

    def perm(self, n, m):
        return self.f[n] * self.g[n - m] % self.mod

    def catalan(self, n):
        return (self.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod
n = II()
mod = 998244353
fact = Factorial(1 << n, mod)
powers = [pow(2, i) for i in range(n - 1, -1, -1)] + [1]
powers_acc = [pow(2, n) - pow(2, i) for i in range(n - 1, -1, -1)]
dp = [0] * (n + 1)
dp[0] = powers[0]
print(0)
for i in range(1, 1 << n):
    new_dp = [0] * (n + 1)
    for j in range(1, n + 1):
        new_dp[j] = (dp[j - 1] * powers[j] + dp[j] * (powers_acc[j - 1] - i + 1)) % mod
    dp = new_dp
    print(dp[-1] * fact.fac((1 << n) - i - 1) * pow(2, n, mod) % mod)

Solution (Python):
import sys
input = sys.stdin.readline
(yes, no) = ('YES', 'NO')
MAXINT = sys.maxsize
e18 = 10 ** 18 + 10
OFFLINE_TEST = False
CHECK_OFFLINE_TEST = True
if CHECK_OFFLINE_TEST:
    import getpass
    OFFLINE_TEST = getpass.getuser() == 'htong'

def log(*args):
    if CHECK_OFFLINE_TEST and OFFLINE_TEST:
        print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
    if OFFLINE_TEST:
        log('----- solving ------')
        log(*args)
        log('----- ------- ------')
    return solve_(*args)

def read_matrix(rows):
    return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
    return [input().strip() for _ in range(rows)]

def minus_one(arr):
    return [x - 1 for x in arr]

def minus_one_matrix(mrr):
    return [[x - 1 for x in row] for row in mrr]
LARGE = 2 ** 20
p = 998244353
factorial_mod_p = [1]
for i in range(1, LARGE + 1):
    factorial_mod_p.append(factorial_mod_p[-1] * i % p)
ifactorial_mod_p = [1] * (LARGE + 1)
ifactorial_mod_p[LARGE] = pow(factorial_mod_p[LARGE], p - 2, p)
for i in range(LARGE - 1, 1, -1):
    ifactorial_mod_p[i] = ifactorial_mod_p[i + 1] * (i + 1) % p

def ncr_mod_p(n, r, p=p):
    if r < 0:
        return 0
    if n < r:
        return 0
    num = factorial_mod_p[n]
    dem = ifactorial_mod_p[r] * ifactorial_mod_p[n - r] % p
    return num * dem % p

def solve_(n):
    n2 = 2 ** n
    dp = [0] * n2
    w = n2 // 2
    dp[0] = 2 * factorial_mod_p[w] % p
    for h in range(n - 2, -1, -1):
        w = 2 ** h
        ndp = [0] * n2
        s = 0
        for i in range(n2):
            ndp[i] = 2 * s * ncr_mod_p(n2 - i - w - 1, w - 1) % p * factorial_mod_p[w] % p
            s += dp[i]
            s %= p
        dp = ndp
    cs = [0]
    for d in dp:
        cs.append((cs[-1] + d) % p)
    for x in cs[:n2]:
        print(x)
for case_num in [0]:
    n = int(input())
    res = solve(n)

Solution (Python):
import sys
input = sys.stdin.readline
(yes, no) = ('YES', 'NO')
MAXINT = sys.maxsize
e18 = 10 ** 18 + 10
OFFLINE_TEST = False
CHECK_OFFLINE_TEST = True
if CHECK_OFFLINE_TEST:
    import getpass
    OFFLINE_TEST = getpass.getuser() == 'htong'

def log(*args):
    if CHECK_OFFLINE_TEST and OFFLINE_TEST:
        print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
    if OFFLINE_TEST:
        log('----- solving ------')
        log(*args)
        log('----- ------- ------')
    return solve_(*args)

def read_matrix(rows):
    return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
    return [input().strip() for _ in range(rows)]

def minus_one(arr):
    return [x - 1 for x in arr]

def minus_one_matrix(mrr):
    return [[x - 1 for x in row] for row in mrr]
LARGE = 2 ** 20
p = 998244353
md = p
n_max = 2 ** 20
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
factorial_mod_p = fac

def ncr_mod_p(n, r, p=p):
    if r < 0:
        return 0
    if n < r:
        return 0
    num = fac[n]
    dem = ifac[r] * ifac[n - r] % p
    return num * dem % p

def solve_(n):
    n2 = 2 ** n
    dp = [0] * n2
    w = n2 // 2
    dp[0] = 2 * factorial_mod_p[w] % p
    for h in range(n - 2, -1, -1):
        w = 2 ** h
        ndp = [0] * n2
        s = 0
        for i in range(n2):
            ndp[i] = 2 * s * ncr_mod_p(n2 - i - w - 1, w - 1) % p * factorial_mod_p[w] % p
            s += dp[i]
            s %= p
        dp = ndp
    cs = [0]
    for d in dp:
        cs.append((cs[-1] + d) % p)
    for x in cs[:n2]:
        print(x)
for case_num in [0]:
    n = int(input())
    res = solve(n)