For problem statement at 1000-1999/1300-1399/1320-1329/1326/problemF1.txt this is a correct solution, but verifier at 1000-1999/1300-1399/1320-1329/1326/verifierF1.go ends with All 100 tests passed can you fix the verifier? package main
import (
"bufio"
"fmt"
"math/bits"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
var n int
fmt.Fscan(reader, &n)
adj := make([]string, n)
for i := 0; i < n; i++ {
fmt.Fscan(reader, &adj[i])
}
dp := make([][]int64, 1<<n)
for i := 0; i < (1 << n); i++ {
dp[i] = make([]int64, n)
}
for i := 0; i < n; i++ {
dp[1<<i][i] = 1
}
for mask := 1; mask < (1 << n); mask++ {
for i := 0; i < n; i++ {
if dp[mask][i] > 0 {
for j := 0; j < n; j++ {
if (mask&(1<<j)) == 0 && adj[i][j] == '1' {
dp[mask|(1<<j)][j] += dp[mask][i]
}
}
}
}
}
C := make([]int64, 1<<n)
for mask := 1; mask < (1 << n); mask++ {
for i := 0; i < n; i++ {
C[mask] += dp[mask][i]
}
}
F := make([][]int64, n+1)
for c := 1; c <= n; c++ {
F[c] = make([]int64, 1<<n)
for mask := 0; mask < (1 << n); mask++ {
if bits.OnesCount32(uint32(mask)) == c {
F[c][mask] = C[mask]
}
}
for i := 0; i < n; i++ {
for mask := 0; mask < (1 << n); mask++ {
if (mask & (1 << i)) != 0 {
F[c][mask] += F[c][mask^(1<<i)]
}
}
}
}
var partitions [][]int
var generatePartitions func(rem int, maxVal int, current []int)
generatePartitions = func(rem int, maxVal int, current []int) {
if rem == 0 {
cp := make([]int, len(current))
copy(cp, current)
partitions = append(partitions, cp)
return
}
for i := maxVal; i >= 1; i-- {
if i <= rem {
generatePartitions(rem-i, i, append(current, i))
}
}
}
generatePartitions(n, n, []int{})
parity := make([]int64, 1<<n)
for mask := 0; mask < (1 << n); mask++ {
if (n-bits.OnesCount32(uint32(mask)))%2 == 1 {
parity[mask] = -1
} else {
parity[mask] = 1
}
}
V := make(map[string]int64)
for _, p := range partitions {
var sum int64 = 0
for mask := 0; mask < (1 << n); mask++ {
var prod int64 = 1
for _, c := range p {
prod *= F[c][mask]
}
sum += prod * parity[mask]
}
V[string(toBytes(p))] = sum
}
f := make([]int64, 1<<(n-1))
for x := 0; x < (1 << (n - 1)); x++ {
var comp []int
cur := 1
for i := 0; i < n-1; i++ {
if (x & (1 << i)) != 0 {
cur++
} else {
comp = append(comp, cur)
cur = 1
}
}
comp = append(comp, cur)
for j := 0; j < len(comp); j++ {
for k := j + 1; k < len(comp); k++ {
if comp[j] < comp[k] {
comp[j], comp[k] = comp[k], comp[j]
}
}
}
f[x] = V[string(toBytes(comp))]
}
for i := 0; i < n-1; i++ {
for x := 0; x < (1 << (n - 1)); x++ {
if (x & (1 << i)) == 0 {
f[x] -= f[x|(1<<i)]
}
}
}
writer := bufio.NewWriter(os.Stdout)
for x := 0; x < (1 << (n - 1)); x++ {
if x > 0 {
writer.WriteString(" ")
}
fmt.Fprint(writer, f[x])
}
writer.WriteString("\n")
writer.Flush()
}
func toBytes(p []int) []byte {
b := make([]byte, len(p))
for i, v := range p {
b[i] = byte(v)
}
return b
}