← Home
For problem statement at 1000-1999/1700-1799/1780-1789/1784/problemD.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1780-1789/1784/verifierD.go ends with All tests passed. can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const MOD = 998244353

func pow(a, b int) int {
	res := 1
	a %= MOD
	for b > 0 {
		if b&1 == 1 {
			res = res * a % MOD
		}
		a = a * a % MOD
		b >>= 1
	}
	return res
}

func ntt(a []int, invert bool) {
	n := len(a)
	j := 0
	for i := 1; i < n; i++ {
		bit := n >> 1
		for j&bit != 0 {
			j ^= bit
			bit >>= 1
		}
		j ^= bit
		if i < j {
			a[i], a[j] = a[j], a[i]
		}
	}
	for l := 2; l <= n; l <<= 1 {
		wlen := pow(3, (MOD-1)/l)
		if invert {
			wlen = pow(wlen, MOD-2)
		}
		for i := 0; i < n; i += l {
			w := 1
			for j := 0; j < l/2; j++ {
				u := a[i+j]
				v := a[i+j+l/2] * w % MOD
				a[i+j] = (u + v) % MOD
				a[i+j+l/2] = (u - v + MOD) % MOD
				w = w * wlen % MOD
			}
		}
	}
	if invert {
		invN := pow(n, MOD-2)
		for i := 0; i < n; i++ {
			a[i] = a[i] * invN % MOD
		}
	}
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	if !scanner.Scan() {
		return
	}
	n, _ := strconv.Atoi(scanner.Text())

	if n == 1 {
		fmt.Println("0 2")
		return
	}

	S := 1 << n
	fact := make([]int, S+1)
	invFact := make([]int, S+1)
	fact[0] = 1
	invFact[0] = 1
	for i := 1; i <= S; i++ {
		fact[i] = fact[i-1] * i % MOD
	}
	invFact[S] = pow(fact[S], MOD-2)
	for i := S - 1; i >= 1; i-- {
		invFact[i] = invFact[i+1] * (i + 1) % MOD
	}

	nCr := func(n, k int) int {
		if k < 0 || k > n {
			return 0
		}
		return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD
	}

	T := (1 << (n - 1)) - 1
	g := make([]int, n)
	g[n-1] = 1

	W := make([]int, T)
	for y := T - 1; y >= 0; y-- {
		W[y] = g[1]
		nextG := make([]int, n)
		for j := 1; j < n; j++ {
			nextG[j] = g[j]
			if j < n-1 {
				req := (1 << j) - 1
				P := y - req
				if P >= req {
					ways := nCr(P, req)
					nextG[j] = (nextG[j] + g[j+1]*ways) % MOD
				}
			}
		}
		g = nextG
	}

	V := make([]int, T+1)
	sum := 0
	for i := 1; i <= T; i++ {
		sum = (sum + W[T-i]) % MOD
		V[i] = sum
	}

	sz := 1
	for sz < 2*(T+1) {
		sz <<= 1
	}
	U := make([]int, sz)
	W_poly := make([]int, sz)
	for i := 0; i <= T; i++ {
		U[i] = V[i] * nCr(T, i) % MOD
		W_poly[i] = nCr(T, i)
	}
	ntt(U, false)
	ntt(W_poly, false)
	for i := 0; i < sz; i++ {
		U[i] = U[i] * W_poly[i] % MOD
	}
	ntt(U, true)

	C := (1 << n) % MOD
	for j := 1; j <= n; j++ {
		C = (C * fact[1<<(j-1)]) % MOD
	}

	ans := make([]int, S+1)
	for k := 1; k <= S; k++ {
		if k < n+1 {
			ans[k] = 0
			continue
		}
		m := k - 2
		Bm := U[m]
		invDenom := pow(nCr(S-2, k-2), MOD-2)
		Ak := Bm * nCr(S-2, T) % MOD * invDenom % MOD
		ans[k] = Ak * C % MOD
	}

	out := bufio.NewWriter(os.Stdout)
	for k := 1; k <= S; k++ {
		if k > 1 {
			out.WriteString(" ")
		}
		out.WriteString(strconv.Itoa(ans[k]))
	}
	out.WriteString("\n")
	out.Flush()
}