UOJ Logo Universal Online Judge

UOJ

#498. 新年的追逐战

附件下载 统计

杰瑞正在被汤姆追捕!

为了摆脱追捕,杰瑞需要知道有地图有多少个老鼠洞可以隐藏!

但两只鞋太太的家实在太大了,为了简单地说明,定义两个简单无向图 $G_{1} =( V_{1} ,E_{1}) ,G_{2} =( V_{2} ,E_{2})$ 的乘积为一个新的图 $G_{1} \times G_{2} =\left( V^{*} ,E^{*} \right)$。

其中新的点集 $V^{*}$ 为:

$$ V^{*} = \left\{{(a,b)| a \in V_{1}, b \in V_{2}}\right\} $$

其中新的边集 $E^{*}$ 为:

$$ E^{*} =\left\{\left(( u_{1} ,v_{1}) ,( u_{2} ,v_{2})\right) \mid ( u_{1} ,u_{2}) \in E_{1}, ( v_{1} ,v_{2}) \in E_{2}\right\} $$

对于正整数 $n$,以及给定的图 $G_{1} ,G_{2} ,\dotsc ,G_{n}$,两只鞋太太的家可以表示成

$$ H = (((G_1 \times G_2) \times G_3) \times \cdots) \times G_n $$

为了方便逃亡(戏弄汤姆),对于同一个连通块,杰瑞事先打通了所有的老鼠洞,你只需要计算一遍。

为了方便逃亡(戏弄汤姆),对于同一个任何一个连通块,都有老鼠洞。

也就是说,你需要求的是 $H$ 的连通块数量。但是杰瑞忘记了每个 $G_k$ 的具体细节,所以我们现在假设每个 $G_k$ 中任意两点间都有 $\frac12$ 的概率连边,求 $H$ 的连通块的期望。显然 $G_k$ 的全体取法共有 ${\large {2^{\binom{m_1}2 + \binom{m_2}2 + \cdots + \binom{m_n}2}}}$ 种。

方便起见,你只需要输出答案乘以 ${\large {2^{\binom{m_1}2 + \binom{m_2}2 + \cdots + \binom{m_n}2}}}$,对 $998244353$ 取模即可。

输入格式

第一行输入一个正整数 $n$。

接下来一行输入 $n$ 个正整数,第 $k$ 个正整数为 $m_k$,表示第 $k$ 个图的顶点数量。

输出格式

输出一个整数,表示答案 $\bmod 998244353$。

样例一

input

1
3

output

13

explanation

注意对于 $n=1$ 的情况,就是枚举所有节点个数为$m_1$的带标号无向图的连通块数量之和。

样例二

input

2
2 3

output

73

explanation

$G_1$ 中有 $0$ 条边的情况下,任何一种 $G_2$ 都会导致 $H$ 中有 $6$ 个连通块,这样的方案共有 $8$ 种。

$G_1$ 中有 $1$ 条边,$G_2$ 中有 $0$ 条边的情况下,$H$ 中有 $6$ 个连通块,这样的方案有 $1$ 种。

$G_1$ 中有 $1$ 条边,$G_2$ 中有 $1$ 条边的情况下,$H$ 中有 $4$ 个连通块,这样的方案有 $3$ 种。

$G_1$ 中有 $1$ 条边,$G_2$ 中有 $2$ 条边的情况下,$H$ 中有 $2$ 个连通块,这样的方案有 $3$ 种。

$G_1$ 中有 $1$ 条边,$G_2$ 中有 $3$ 条边的情况下,$H$ 中有 $1$ 个连通块,这样的方案有 $1$ 种。 $$ 6\times 8 + 6\times 1 + 4\times 3 + 2\times 3 + 1\times 1 = 73 $$

样例三

input

2
4 4

output

21565

限制与约定

测试点编号$n$$m_k$
$1$$\le 4$$\le 4$
$2$$ = 1$$\le 10^3$
$3$$ = 1$$\le 10^5$
$4$$ = 2$$\le 10^3$
$5$$ = 2$$\le 10^5$
$6$$\le 10^3$$\le 10^3$
$7$$\le 10^5$$\le 10^3$
$8$$\le 10^5$$\le 10^5$
$9$$\le 10^5$$\le 10^5$
$10$$\le 10^5$$\le 10^5$

对于所有测试数据,满足 $1\le n, m_k\le 10^5$。

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$

下载

样例数据下载