AT_abc310_f [ABC310F] Make 10 Again

题目描述

有 $N$ 个骰子。对于 $i = 1, 2, \ldots, N$，第 $i$ 个骰子掷出时，会以等概率随机出现 $1$ 到 $A_i$ 之间的任意一个整数。

当同时掷出这 $N$ 个骰子时，求满足下述条件的概率对 $998244353$ 取模的结果。

存在一种选择若干个（也可以全部）骰子的方式，使得所选骰子的点数之和恰好等于 $10$。

概率 $\bmod\ 998244353$ 的定义如下：本题要求的概率一定是有理数。并且，在本题的约束下，若将概率表示为最简分数 $\frac{y}{x}$，保证 $x$ 不会被 $998244353$ 整除。

此时，存在唯一的 $0$ 到 $998244352$ 之间的整数 $z$，使得 $xz \equiv y \pmod{998244353}$。请输出这个 $z$。

输入格式

输入以如下格式从标准输入读入。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4
1 7 2 9

输出 #1

942786334

输入输出样例 #2

输入 #2

7
1 10 100 1000 10000 100000 1000000

输出 #2

996117877

说明/提示

约束条件

• $1 \leq N \leq 100$
• $1 \leq A_i \leq 10^6$
• 输入均为整数

样例解释 1

例如，当第 $1, 2, 3, 4$ 个骰子的点数分别为 $1, 3, 2, 7$ 时，这种结果满足题目中的条件。实际上，选择第 $2, 4$ 个骰子时，点数之和为 $3 + 7 = 10$。另外，选择第 $1, 3, 4$ 个骰子时，点数之和也为 $1 + 2 + 7 = 10$。

另一方面，当第 $1, 2, 3, 4$ 个骰子的点数分别为 $1, 6, 1, 5$ 时，无论如何选择骰子，都无法使所选骰子的点数之和为 $10$，因此这种结果不满足题目中的条件。

在本输入样例中，掷出 $N$ 个骰子的结果满足题目条件的概率为 $\frac{11}{18}$。因此，其对 $998244353$ 取模后的值为 $942786334$。

由 ChatGPT 4.1 翻译