← Home
For problem statement at 0-999/200-299/290-299/293/problemB.txt this is a correct solution, but verifier at 0-999/200-299/290-299/293/verifierB.go ends with All 100 tests passed can you fix the verifier? package main

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

func canonicalize(state uint64, F, k int) uint64 {
	var u [10]int
	for c := F; c < k; c++ {
		u[c-F] = int((state >> (4 * c)) & 15)
	}
	U := k - F
	for i := 1; i < U; i++ {
		tmp := u[i]
		j := i - 1
		for j >= 0 && u[j] > tmp {
			u[j+1] = u[j]
			j--
		}
		u[j+1] = tmp
	}
	for c := F; c < k; c++ {
		state = (state &^ (uint64(15) << (4 * c))) | (uint64(u[c-F]) << (4 * c))
	}
	return state
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n, m, k int
	if _, err := fmt.Fscan(reader, &n, &m, &k); err != nil {
		return
	}

	grid := make([][]int, n)
	for i := 0; i < n; i++ {
		grid[i] = make([]int, m)
		for j := 0; j < m; j++ {
			fmt.Fscan(reader, &grid[i][j])
		}
	}

	if n+m-1 > k {
		fmt.Println(0)
		return
	}

	present := make([]bool, k+1)
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] > 0 {
				present[grid[i][j]] = true
			}
		}
	}

	colorMap := make(map[int]int)
	F := 0
	for c := 1; c <= k; c++ {
		if present[c] {
			colorMap[c] = F
			F++
		}
	}

	dp := make(map[uint64]int64)
	initial_state := uint64(0)
	for c := 0; c < k; c++ {
		initial_state |= uint64(m) << (4 * c)
	}
	dp[initial_state] = 1

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			next_dp := make(map[uint64]int64)
			req := grid[i][j]

			var req_idx int
			if req > 0 {
				req_idx = colorMap[req]
			}

			for state, count := range dp {
				if req > 0 {
					val := int((state >> (4 * req_idx)) & 15)
					if val > j {
						next_state := (state &^ (uint64(15) << (4 * req_idx))) | (uint64(j) << (4 * req_idx))
						next_dp[next_state] = (next_dp[next_state] + count) % 1000000007
					}
				} else {
					for c := 0; c < F; c++ {
						val := int((state >> (4 * c)) & 15)
						if val > j {
							next_state := (state &^ (uint64(15) << (4 * c))) | (uint64(j) << (4 * c))
							next_dp[next_state] = (next_dp[next_state] + count) % 1000000007
						}
					}

					for c := F; c < k; c++ {
						val := int((state >> (4 * c)) & 15)
						if val > j {
							if c > F && int((state>>(4*(c-1)))&15) == val {
								continue
							}
							freq := 0
							for idx := F; idx < k; idx++ {
								if int((state>>(4*idx))&15) == val {
									freq++
								}
							}
							next_state := (state &^ (uint64(15) << (4 * c))) | (uint64(j) << (4 * c))
							next_state = canonicalize(next_state, F, k)
							ways := (count * int64(freq)) % 1000000007
							next_dp[next_state] = (next_dp[next_state] + ways) % 1000000007
						}
					}
				}
			}
			dp = next_dp
		}
	}

	ans := int64(0)
	for _, count := range dp {
		ans = (ans + count) % 1000000007
	}
	fmt.Println(ans)
}