← Home
For problem statement at 1000-1999/1000-1099/1080-1089/1085/problemG.txt this is a correct solution, but verifier at 1000-1999/1000-1099/1080-1089/1085/verifierG.go ends with REFERENCE_SOURCE_PATH not set
exit status 1 can you fix the verifier? package main

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

const MOD int64 = 998244353

func add(bit []int, idx, delta int) {
	n := len(bit) - 1
	for idx <= n {
		bit[idx] += delta
		idx += idx & -idx
	}
}

func sum(bit []int, idx int) int {
	s := 0
	for idx > 0 {
		s += bit[idx]
		idx -= idx & -idx
	}
	return s
}

func buildAllOnesBIT(n int) []int {
	bit := make([]int, n+1)
	for i := 1; i <= n; i++ {
		bit[i] = 1
	}
	for i := 1; i <= n; i++ {
		j := i + (i & -i)
		if j <= n {
			bit[j] += bit[i]
		}
	}
	return bit
}

func rankPerm(row []int, fact []int64, baseOnes []int) int64 {
	n := len(row)
	bit := make([]int, n+1)
	copy(bit, baseOnes)
	var rank int64
	for i, v := range row {
		smaller := sum(bit, v-1)
		rank += int64(smaller) * fact[n-1-i]
		rank %= MOD
		add(bit, v, -1)
	}
	return rank
}

func rankAdj(prev, cur []int, f [][]int64, baseOnes []int) int64 {
	n := len(prev)
	pos := make([]int, n+1)
	for i, v := range prev {
		pos[v] = i + 1
	}

	bitU := make([]int, n+1)
	copy(bitU, baseOnes)

	bitF := make([]int, n+1)
	for i := 1; i < n; i++ {
		bitF[prev[i]] = 1
	}
	for i := 1; i <= n; i++ {
		j := i + (i & -i)
		if j <= n {
			bitF[j] += bitF[i]
		}
	}

	used := make([]bool, n+1)
	K := n
	var rank int64

	for i := 1; i <= n; i++ {
		pi := prev[i-1]
		qi := cur[i-1]

		ai := 0
		if !used[pi] {
			ai = 1
		}

		smallerAll := sum(bitU, qi-1)
		smallerFuture := sum(bitF, qi-1)

		excludePi := 0
		if !used[pi] && pi < qi {
			excludePi = 1
		}

		cnt0 := smallerAll - smallerFuture - excludePi
		cnt1 := smallerFuture

		m := n - i
		k0 := K - ai

		if cnt0 != 0 {
			rank += int64(cnt0) * f[m][k0]
		}
		if cnt1 != 0 {
			rank += int64(cnt1) * f[m][k0-1]
		}
		rank %= MOD

		used[qi] = true
		add(bitU, qi, -1)
		if pos[qi] > i {
			add(bitF, qi, -1)
		}

		K -= ai
		if pos[qi] > i {
			K--
		}

		if i < n {
			y := prev[i]
			if !used[y] {
				add(bitF, y, -1)
			}
		}
	}

	return rank
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	idx := 0
	nextInt := func() int {
		for idx < len(data) && (data[idx] < '0' || data[idx] > '9') {
			idx++
		}
		v := 0
		for idx < len(data) && data[idx] >= '0' && data[idx] <= '9' {
			v = v*10 + int(data[idx]-'0')
			idx++
		}
		return v
	}

	n := nextInt()

	fact := make([]int64, n+1)
	fact[0] = 1
	for i := 1; i <= n; i++ {
		fact[i] = fact[i-1] * int64(i) % MOD
	}

	f := make([][]int64, n+1)
	f[0] = []int64{1}
	for m := 1; m <= n; m++ {
		f[m] = make([]int64, m+1)
		f[m][0] = fact[m]
		for k := 1; k <= m; k++ {
			v := f[m][k-1] - f[m-1][k-1]
			if v < 0 {
				v += MOD
			}
			f[m][k] = v
		}
	}

	der := f[n][n]
	powD := make([]int64, n+1)
	powD[0] = 1
	for i := 1; i <= n; i++ {
		powD[i] = powD[i-1] * der % MOD
	}

	baseOnes := buildAllOnesBIT(n)

	prev := make([]int, n)
	for i := 0; i < n; i++ {
		prev[i] = nextInt()
	}

	ans := rankPerm(prev, fact, baseOnes) * powD[n-1] % MOD

	for r := 2; r <= n; r++ {
		cur := make([]int, n)
		for i := 0; i < n; i++ {
			cur[i] = nextInt()
		}
		val := rankAdj(prev, cur, f, baseOnes) * powD[n-r] % MOD
		ans += val
		ans %= MOD
		prev = cur
	}

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	fmt.Fprint(out, ans)
	out.Flush()
}