For problem statement at 2000-2999/2000-2099/2030-2039/2038/problemF.txt this is a correct solution, but verifier at 2000-2999/2000-2099/2030-2039/2038/verifierF.go ends with All 153 tests passed. can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
"sort"
)
const MOD = 998244353
func power(base, exp int64) int64 {
res := int64(1)
base %= MOD
for exp > 0 {
if exp%2 == 1 {
res = (res * base) % MOD
}
base = (base * base) % MOD
exp /= 2
}
return res
}
func modInverse(n int64) int64 {
return power(n, MOD-2)
}
func ntt(a []int64, 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 length := 2; length <= n; length <<= 1 {
wlen := power(3, (MOD-1)/int64(length))
if invert {
wlen = modInverse(wlen)
}
for i := 0; i < n; i += length {
w := int64(1)
for j := 0; j < length/2; j++ {
u := a[i+j]
v := (a[i+j+length/2] * w) % MOD
a[i+j] = u + v
if a[i+j] >= MOD {
a[i+j] -= MOD
}
a[i+j+length/2] = u - v + MOD
if a[i+j+length/2] >= MOD {
a[i+j+length/2] -= MOD
}
w = (w * wlen) % MOD
}
}
}
if invert {
nInv := modInverse(int64(n))
for i := 0; i < n; i++ {
a[i] = (a[i] * nInv) % MOD
}
}
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
var scanner *bufio.Scanner
func init() {
scanner = bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
scanner.Buffer(make([]byte, 1024*1024), 10*1024*1024)
}
func nextInt() int {
scanner.Scan()
res := 0
b := scanner.Bytes()
for _, v := range b {
res = res*10 + int(v-'0')
}
return res
}
func main() {
if !scanner.Scan() {
return
}
n := 0
b := scanner.Bytes()
for _, v := range b {
n = n*10 + int(v-'0')
}
v := make([]int, n+1)
r := make([]int, n+1)
m := make([]int, n+1)
for i := 1; i <= n; i++ {
v[i] = nextInt()
}
for i := 1; i <= n; i++ {
r[i] = nextInt()
m[i] = min(v[i], r[i])
}
sort.Ints(v)
sort.Ints(r)
sort.Ints(m)
fact := make([]int64, n+1)
invFact := make([]int64, n+1)
fact[0] = 1
invFact[0] = 1
for i := 1; i <= n; i++ {
fact[i] = (fact[i-1] * int64(i)) % MOD
}
invFact[n] = modInverse(fact[n])
for i := n - 1; i >= 1; i-- {
invFact[i] = (invFact[i+1] * int64(i+1)) % MOD
}
size := 1
for size <= 2*n {
size <<= 1
}
A_poly := make([]int64, size)
B_poly := make([]int64, size)
for c := 0; c <= n; c++ {
var ac int64
if c > 0 {
ac = int64(v[n-c+1] - v[n-c] + r[n-c+1] - r[n-c] - (m[n-c+1] - m[n-c]))
ac %= MOD
if ac < 0 {
ac += MOD
}
}
A_poly[n-c] = (ac * fact[c]) % MOD
B_poly[c] = invFact[c]
}
ntt(A_poly, false)
ntt(B_poly, false)
C_poly := make([]int64, size)
for i := 0; i < size; i++ {
C_poly[i] = (A_poly[i] * B_poly[i]) % MOD
}
ntt(C_poly, true)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
for k := 1; k <= n; k++ {
ans := C_poly[n-k]
ans = (ans * fact[n-k]) % MOD
ans = (ans * invFact[n]) % MOD
fmt.Fprint(out, ans, " ")
}
fmt.Fprintln(out)
}