← Home
For problem statement at 1000-1999/1700-1799/1730-1739/1731/problemF.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1730-1739/1731/verifierF.go ends with All 100 tests passed can you fix the verifier? package main

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

const MOD int64 = 998244353

func modPow(a, e int64) int64 {
	res := int64(1)
	for e > 0 {
		if e&1 == 1 {
			res = res * a % MOD
		}
		a = a * a % MOD
		e >>= 1
	}
	return res
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n int
	var k int64
	fmt.Fscan(in, &n, &k)

	m := n + 1

	var comb [55][55]int64
	for i := 0; i <= n; i++ {
		comb[i][0], comb[i][i] = 1, 1
		for j := 1; j < i; j++ {
			comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
			if comb[i][j] >= MOD {
				comb[i][j] -= MOD
			}
		}
	}

	var pw [55][55]int64
	for b := 0; b <= m; b++ {
		pw[b][0] = 1
		for e := 1; e <= n; e++ {
			pw[b][e] = pw[b][e-1] * int64(b) % MOD
		}
	}

	y := make([]int64, m+1)
	for t := 0; t <= m; t++ {
		ans := int64(0)
		for i := 1; i <= n; i++ {
			l := i - 1
			r := n - i
			var prefA [55]int64
			for x := 1; x <= t; x++ {
				less := x - 1
				ge := t - x + 1
				greater := t - x
				le := x

				run := int64(0)
				for u := 0; u <= l; u++ {
					a := comb[l][u] * pw[less][u] % MOD * pw[ge][l-u] % MOD
					run += a
					if run >= MOD {
						run -= MOD
					}
					prefA[u] = run
				}

				total := int64(0)
				for v := 1; v <= r; v++ {
					b := comb[r][v] * pw[greater][v] % MOD * pw[le][r-v] % MOD
					idx := v - 1
					if idx > l {
						idx = l
					}
					total += b * prefA[idx] % MOD
					if total >= MOD {
						total -= MOD
					}
				}

				ans += int64(x) * total % MOD
				if ans >= MOD {
					ans -= MOD
				}
			}
		}
		y[t] = ans
	}

	if k <= int64(m) {
		fmt.Fprintln(out, y[int(k)])
		return
	}

	fact := make([]int64, m+1)
	invFact := make([]int64, m+1)
	fact[0] = 1
	for i := 1; i <= m; i++ {
		fact[i] = fact[i-1] * int64(i) % MOD
	}
	invFact[m] = modPow(fact[m], MOD-2)
	for i := m; i >= 1; i-- {
		invFact[i-1] = invFact[i] * int64(i) % MOD
	}

	pref := make([]int64, m+2)
	suff := make([]int64, m+2)
	pref[0] = 1
	for i := 0; i <= m; i++ {
		v := k - int64(i)
		if v < 0 {
			v += MOD
		}
		pref[i+1] = pref[i] * v % MOD
	}
	suff[m+1] = 1
	for i := m; i >= 0; i-- {
		v := k - int64(i)
		if v < 0 {
			v += MOD
		}
		suff[i] = suff[i+1] * v % MOD
	}

	ans := int64(0)
	for i := 0; i <= m; i++ {
		term := y[i] * pref[i] % MOD * suff[i+1] % MOD * invFact[i] % MOD * invFact[m-i] % MOD
		if (m-i)&1 == 1 {
			term = (MOD - term) % MOD
		}
		ans += term
		if ans >= MOD {
			ans -= MOD
		}
	}

	fmt.Fprintln(out, ans)
}