Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has a combination lock with $N$ wheels (numbered $1$ through $N$). For each valid $i$, on the $i$-th wheel, the integers from $0$ to $A_{i}$ (inclusive) are written in ascending order ($0$ and $A_{i}$ are also adjacent). Initially, one value on each wheel is selected uniformly randomly and independently.

The lock operates in a very peculiar way: it opens when there is at least one wheel where either $0$ or the largest value on that wheel is selected. Chef wants to open the lock using the smallest possible number of operations; in one operation, he may choose one wheel and rotate it clockwise or counterclockwise by $1$ unit (i.e. select a value that is adjacent to the previously selected value on that wheel).

Find the [expected value] of the number of operations which Chef needs to perform to open the lock.

The expected number of operations can be represented as a fraction $\frac{P}{Q}$, where $P$ is a non-negative integer and $Q$ a positive integer coprime with $998,244,353$. You should calculate $P \cdot Q^{-1}$ modulo $998,244,353$, where $Q^{-1}$ denotes the multiplicative inverse of $Q$ modulo $998,244,353$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer $P \cdot Q^{-1}$ modulo $998,244,353$.

------  Constraints ------
$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} < 998,244,352$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{5}$

------  Subtasks ------
Subtask #1 (10 points):
$N ≤ 5,000$
$A_{i} ≤ 5,000$ for each valid $i$
the sum of $N$ over all test cases does not exceed $5,000$

Subtask #2 (20 points):
$N ≤ 5,000$
the sum of $N$ over all test cases does not exceed $5,000$

Subtask #3 (70 points): original constraints

----- Sample Input 1 ------ 
3

2

2 2

2

5 5

3

3 4 5
----- Sample Output 1 ------ 
443664157

221832079

598946612

Source: codechef | Difficulty: VERY_HARD
Tags: Polynomials and generating functions

Matrices

Mathematics


Solutions:
from random import *
import time

def ilog2(n):
	return 0 if n <= 0 else n.bit_length() - 1

def pack(pack, shamt):
	size = len(pack)
	while size > 1:
		npack = []
		for i in range(0, size - 1, 2):
			npack += [pack[i] | pack[i + 1] << shamt]
		if size & 1:
			npack += [pack[-1]]
		(pack, size, shamt) = (npack, size + 1 >> 1, shamt << 1)
	return pack[0]

def unpack(M, size, shamt):
	(s, sizes) = (size, [])
	while s > 1:
		sizes += [s]
		s = s + 1 >> 1
	ret = [M]
	for size in sizes[::-1]:
		(mask, nret) = ((1 << shamt) - 1, [])
		for c in ret:
			nret += [c & mask, c >> shamt]
		(ret, shamt) = (nret[:size], shamt >> 1)
	return ret

def poly_mul_mod(f, g, mod):
	size = min(len(f), len(g))
	shift = ((mod - 1) ** 2 * size).bit_length()
	rsize = len(f) + len(g) - 1
	h = unpack(pack(f, shift) * pack(g, shift), rsize, shift * (1 << ilog2(rsize - 1)))
	return [int(x % mod) for x in h]

def poly_inverse_mod(f, size, mod):
	assert f[0] == 1
	(deg, degs) = (size - 1, [])
	while deg > 0:
		degs += [deg]
		deg >>= 1
	f2 = f[:]
	if len(f2) < size:
		f2.extend([0] * (size - len(f2)))
	inv = [1]
	for t in degs[::-1]:
		s = t + 1 - len(inv)
		tmp = poly_mul_mod(f2[:t + 1], inv, mod)[len(inv):]
		tmp = poly_mul_mod(tmp[:s], inv[:s], mod)
		inv.extend([-v % mod for v in tmp[:s]])
	return inv

def inv(a, b):
	return pow(a, b - 2, b)
MOD = 998244353

def multiply(A):
	if len(A) == 1:
		return A[0]
	mid = len(A) // 2
	return poly_mul_mod(multiply(A[:mid]), multiply(A[mid:]), MOD)

def sum_of_powers(N, n):
	(A, B) = ([0] * n, [0] * n)
	A[0] = 1
	B[0] = N
	P = (N + 1) % MOD
	for i in range(1, n):
		A[i] = A[i - 1] * inv(i + 1, MOD) % MOD
		P = P * (N + 1) % MOD
		B[i] = (P - 1) * A[i] % MOD
	F = poly_mul_mod(B, poly_inverse_mod(A, n, MOD), MOD)[:n]
	P = 1
	for i in range(1, n):
		P = P * i % MOD
		F[i] = F[i] * P % MOD
	return F
for testcase in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	D = (min(A) + 1) // 2
	power_sums = sum_of_powers(D, n + 1)
	B = multiply([[a + 1, MOD - 2] for a in A])
	(ans, X) = (0, 1)
	for i in range(n + 1):
		if i < n:
			X = X * (A[i] + 1) % MOD
		ans += B[i] * power_sums[i]
	print(ans * inv(X, MOD) % MOD)