← Home
For problem statement at 1000-1999/1200-1299/1250-1259/1251/problemF.txt this is a correct solution, but verifier at 1000-1999/1200-1299/1250-1259/1251/verifierF.go ends with All tests passed. can you fix the verifier? package main

import (
	"io"
	"os"
	"strconv"
)

const MOD int64 = 998244353
const MAXV int = 300000

func nextInt(data []byte, idx *int) int {
	n := len(data)
	for *idx < n {
		c := data[*idx]
		if c >= '0' && c <= '9' {
			break
		}
		*idx = *idx + 1
	}
	val := 0
	for *idx < n {
		c := data[*idx]
		if c < '0' || c > '9' {
			break
		}
		val = val*10 + int(c-'0')
		*idx = *idx + 1
	}
	return val
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	idx := 0

	n := nextInt(data, &idx)
	k := nextInt(data, &idx)

	freq := make([]int, MAXV+1)
	for i := 0; i < n; i++ {
		x := nextInt(data, &idx)
		freq[x]++
	}

	reds := make([]int, k)
	for i := 0; i < k; i++ {
		reds[i] = nextInt(data, &idx)
	}

	q := nextInt(data, &idx)
	queries := make([]int, q)
	maxHalf := 0
	for i := 0; i < q; i++ {
		x := nextInt(data, &idx)
		queries[i] = x
		if x/2 > maxHalf {
			maxHalf = x / 2
		}
	}

	pref1 := make([]int, MAXV+1)
	pref2 := make([]int, MAXV+1)
	for i := 1; i <= MAXV; i++ {
		pref1[i] = pref1[i-1]
		pref2[i] = pref2[i-1]
		if freq[i] == 1 {
			pref1[i]++
		} else if freq[i] >= 2 {
			pref2[i]++
		}
	}

	inv := make([]int64, n+1)
	if n >= 1 {
		inv[1] = 1
		for i := 2; i <= n; i++ {
			inv[i] = MOD - (MOD/int64(i))*inv[int(MOD%int64(i))]%MOD
		}
	}

	ans := make([]int64, maxHalf+1)

	for _, red := range reds {
		base := red + 1
		if base > maxHalf {
			continue
		}

		p := red - 1
		A, c2 := 0, 0
		if p > 0 {
			A = pref1[p]
			c2 = pref2[p]
		}
		B := 2 * c2
		deg := A + B

		limit := maxHalf - base
		if limit > deg {
			limit = deg
		}

		ans[base]++
		if ans[base] >= MOD {
			ans[base] -= MOD
		}

		if limit >= 1 {
			prev := int64(1)
			cur := int64(2*A + B)
			ans[base+1] += cur
			if ans[base+1] >= MOD {
				ans[base+1] -= MOD
			}

			coef0 := 2*A + B
			for t := 1; t < limit; t++ {
				c1 := int64(coef0 - 3*t)
				if c1 < 0 {
					c1 += MOD
				}
				c2v := int64(2 * (deg - t + 1))
				next := (c1*cur + c2v*prev) % MOD
				next = next * inv[t+1] % MOD

				pos := base + t + 1
				ans[pos] += next
				if ans[pos] >= MOD {
					ans[pos] -= MOD
				}

				prev, cur = cur, next
			}
		}
	}

	out := make([]byte, 0, q*12)
	for i, x := range queries {
		if i > 0 {
			out = append(out, '\n')
		}
		out = strconv.AppendInt(out, ans[x/2], 10)
	}
	os.Stdout.Write(out)
}