For problem statement at 1000-1999/1400-1499/1470-1479/1473/problemG.txt this is a correct solution, but verifier at 1000-1999/1400-1499/1470-1479/1473/verifierG.go ends with case 2 failed: oracle error: exit status 2
input:
3
2 3
2 3
3 3 can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
)
const MOD = 998244353
const G = 3
const MAX = 200010
var fact, invFact [MAX]int64
func powMod(a, b int64) int64 {
res := int64(1)
a %= MOD
for b > 0 {
if b&1 == 1 {
res = res * a % MOD
}
a = a * a % MOD
b >>= 1
}
return res
}
func precompute() {
fact[0] = 1
invFact[0] = 1
for i := 1; i < MAX; i++ {
fact[i] = fact[i-1] * int64(i) % MOD
}
invFact[MAX-1] = powMod(fact[MAX-1], MOD-2)
for i := MAX - 2; i >= 1; i-- {
invFact[i] = invFact[i+1] * int64(i+1) % MOD
}
}
func nCr(n, r int) int64 {
if r < 0 || r > n {
return 0
}
return fact[n] * invFact[r] % MOD * invFact[n-r] % MOD
}
func ntt(arr []int64, invert bool) {
n := len(arr)
for i, j := 1, 0; i < n; i++ {
bit := n >> 1
for j&bit != 0 {
j ^= bit
bit >>= 1
}
j ^= bit
if i < j {
arr[i], arr[j] = arr[j], arr[i]
}
}
for l := 2; l <= n; l <<= 1 {
wlen := powMod(G, (MOD-1)/int64(l))
if invert {
wlen = powMod(wlen, MOD-2)
}
for i := 0; i < n; i += l {
w := int64(1)
for j := 0; j < l/2; j++ {
u := arr[i+j]
v := arr[i+j+l/2] * w % MOD
arr[i+j] = u + v
if arr[i+j] >= MOD {
arr[i+j] -= MOD
}
arr[i+j+l/2] = u - v + MOD
if arr[i+j+l/2] >= MOD {
arr[i+j+l/2] -= MOD
}
w = w * wlen % MOD
}
}
}
if invert {
nInv := powMod(int64(n), MOD-2)
for i := range arr {
arr[i] = arr[i] * nInv % MOD
}
}
}
func main() {
precompute()
reader := bufio.NewReader(os.Stdin)
var n int
if _, err := fmt.Fscan(reader, &n); err != nil {
return
}
a_in := make([]int, n+1)
b_in := make([]int, n+1)
for i := 1; i <= n; i++ {
fmt.Fscan(reader, &a_in[i], &b_in[i])
}
A := make([]int64, 32768)
B := make([]int64, 32768)
DP := make([]int64, 1)
DP[0] = 1
W_curr := 0
for i := 1; i <= n; i++ {
W_next := W_curr + a_in[i] - b_in[i]
sz := 1
for sz <= 2*W_curr+W_next {
sz <<= 1
}
if sz > len(A) {
A = make([]int64, sz)
B = make([]int64, sz)
}
for j := 0; j < sz; j++ {
A[j] = 0
B[j] = 0
}
for j := 0; j <= W_curr; j++ {
A[j] = DP[j]
}
for m := 0; m <= W_curr+W_next; m++ {
B[m] = nCr(a_in[i]+b_in[i], b_in[i]+m-W_curr)
}
ntt(A[:sz], false)
ntt(B[:sz], false)
for j := 0; j < sz; j++ {
A[j] = A[j] * B[j] % MOD
}
ntt(A[:sz], true)
nextDP := make([]int64, W_next+1)
for nj := 0; nj <= W_next; nj++ {
nextDP[nj] = A[nj+W_curr]
}
DP = nextDP
W_curr = W_next
}
ans := int64(0)
for _, val := range DP {
ans = (ans + val) % MOD
}
fmt.Println(ans)
}