#P18497. Bridge Elimination
Bridge Elimination
Bridge Elimination
有一张包含 个顶点的无向图,顶点编号为 。顶点 上写有整数 。最初图中没有边,你可以自由添加边。
共有 种添加边使结果为简单图的方法。对每种方法得到的图,按以下规则计算分数,求所有这些分数之和模 的值:
- 如果图不连通,分数为 。
- 如果图连通,删除原图中的全部桥,得到图 。对 的每个连通分量,求其中顶点上整数的和,再将这些和全部相乘,作为该图的分数。
这里桥是删除后使图的连通分量数增加的边。图为简单图,即没有自环或重边。
输入格式
N
A1 A2 ... AN
所有输入值均为整数,满足 ,。只有一个测试用例。
输出格式
输出所有图的分数之和模 的值。
样例 1
输入:
3
8 5 9
输出:
1102
三点的简单连通无向图共有以下四种。下面四图均直接取自官方原题:

它们的分数分别为 ,因此答案为 。前三图的全部边都是桥;最后一图没有桥。
样例 2
输入:
5
4 2 1 3 10
输出:
63860
样例 3
输入:
7
229520041 118275986 281963154 784360383 478705114 655222915 970715006
输出:
35376232