← Home
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
}