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()
}