各項の寄与を考えてみましょう.
問題原案:kusirakusira
であり,現実的な実行時間で の要素をすべて列挙して答えを求めることは不可能です.
そこで, の各項が答えにどれだけ影響を与えるかを求め,それをすべての項に対して合計することを考えます.
とします.
項目 ( とします) を固定したとき,その他の項の値の組み合わせとしてありうるものは 通りです.
そして,その 通りについて の場合をそれぞれ考え,その総和を求めればよいので,結局 項目の寄与は以下に等しいです:
これを各 について足し合わせたものが答えであり,これは 時間などで求められます.
解説:uni_kakurenbo
xxxxxxxxxx
from functools import reduce
MOD = 998244353
INV_2 = 499122177 # mod 998244353 における 2 の逆元
for _ in range(int(input())):
n = int(input())
A = [*map(int, input().split())]
p = reduce(lambda a, b: a * b % MOD, A)
print(p * reduce(lambda a, b: (a + b) % MOD, (a + 1 for a in A)) * INV_2 % MOD)