#P18497. Bridge Elimination

Bridge Elimination

Bridge Elimination

有一张包含 NN 个顶点的无向图,顶点编号为 1,2,…,N1,2,\ldots,N。顶点 ii 上写有整数 AiA_i。最初图中没有边,你可以自由添加边。

共有 2N(N−1)/22^{N(N-1)/2} 种添加边使结果为简单图的方法。对每种方法得到的图,按以下规则计算分数,求所有这些分数之和模 998244353998244353 的值:

  • 如果图不连通,分数为 00。
  • 如果图连通,删除原图中的全部桥,得到图 GG。对 GG 的每个连通分量,求其中顶点上整数的和,再将这些和全部相乘,作为该图的分数。

这里桥是删除后使图的连通分量数增加的边。图为简单图,即没有自环或重边。

输入格式

N
A1 A2 ... AN

所有输入值均为整数,满足 1≤N≤4001\le N\le400,0≤Ai<9982443530\le A_i<998244353。只有一个测试用例。

输出格式

输出所有图的分数之和模 998244353998244353 的值。

样例 1

输入:

3
8 5 9

输出:

1102

三点的简单连通无向图共有以下四种。下面四图均直接取自官方原题:

第一张连通图 第二张连通图 第三张连通图 第四张连通图

它们的分数分别为 360,360,360,22360,360,360,22,因此答案为 11021102。前三图的全部边都是桥;最后一图没有桥。

样例 2

输入:

5
4 2 1 3 10

输出:

63860

样例 3

输入:

7
229520041 118275986 281963154 784360383 478705114 655222915 970715006

输出:

35376232