F - Figures

Contest Duration: 2020-10-24(Sat) 12:00 - 2020-10-24(Sat) 13:40 (local time) (100 minutes) Back to Home

F - Figures Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $800$ 点

問題文

高橋君はフィギュアを組み立てようとしています。このフィギュアは、 $N$ 個の部品(部品 $1$ , 部品 $2$ , ..., 部品 $N$ )と、 $N-1$ 個の接続用部品から成ります。部品同士は区別が出来ますが、接続用部品同士は区別が出来ません。

部品 $i$ には、 $d_i$ 個の接続用部品を挿す穴(穴 $1$ , 穴 $2$ , ..., 穴 $d_i$ )が空いています。各部品の穴同士は区別が出来ます。各接続用部品は、 $2$ 個の部品の穴に挿し込まれ、それら $2$ 個の部品を接続します。 $1$ つの穴に複数の接続用部品を挿し込むことは出来ません。

以下の性質を満たすフィギュアのことを、完成形と呼びます。

$N-1$ 個の接続用部品が全て部品の接続に使われている。
部品を頂点とし、接続用部品で接続された部品に対応する頂点組に辺が存在する $N$ 頂点 $N-1$ 辺の無向グラフを考えた際に、このグラフは連結である。

$2$ つの完成形について、全ての穴の組についてその $2$ つを接続する接続用部品が存在するか否かが一致するとき、 $2$ つの完成形が同じであると見なします。

完成形が何種類あるかを答えてください。ただし、答えは非常に大きくなることがあるので、 $998244353$ で割った余りを出力してください。

制約

入力は全て整数
$2 \leq N \leq 2 \times 10^5$
$1 \leq d_i < 998244353$

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $d_1$   $d_2$   $\cdots$   $d_N$

出力

答えを出力せよ。

入力例 1Copy

Copy

3
1 1 3

出力例 1Copy

Copy

例えば、部品 $1$ の穴 $1$ と部品 $3$ の穴 $3$ を接続し、部品 $2$ の穴 $1$ と部品 $3$ の穴 $1$ を接続したフィギュアは、完成形として認められます。

入力例 2Copy

Copy

3
1 1 1

出力例 2Copy

Copy

入力例 3Copy

Copy

6
7 3 5 10 6 4

出力例 3Copy

Copy

389183858

入力例 4Copy

Copy

9
425656 453453 4320 1231 9582 54336 31435436 14342 423543

出力例 4Copy

Copy

667877982

Score : $800$ points

Problem Statement

Takahashi is about to assemble a character figure, consisting of $N$ parts called Part $1$ , Part $2$ , ..., Part $N$ and $N-1$ connecting components. Parts are distinguishable, but connecting components are not.

Part $i$ has $d_i$ holes, called Hole $1$ , Hole $2$ , ..., Hole $d_i$ , into which a connecting component can be inserted. These holes in the parts are distinguishable. Each connecting component will be inserted into two holes in different parts, connecting these two parts. It is impossible to insert multiple connecting components into a hole.

The character figure is said to be complete when it has the following properties:

All of the $N-1$ components are used to connect parts.
Consider a graph with $N$ vertices corresponding to the parts and $N-1$ undirected edges corresponding to the pairs of vertices connected by a connecting component. Then, this graph is connected.

Two ways A and B to make the figure complete are considered the same when the following is satisfied: for every pair of holes, A uses a connecting component to connect these holes if and only if B uses one to connect them.

Find the number of ways to make the figure complete. Since the answer can be enormous, find the count modulo $998244353$ .

Constraints

All values in input are integers.
$2 \leq N \leq 2 \times 10^5$
$1 \leq d_i < 998244353$

Input

Input is given from Standard Input in the following format:

 $N$ 
 $d_1$   $d_2$   $\cdots$   $d_N$

Output

Print the answer.

Sample Input 1Copy

Copy

3
1 1 3

Sample Output 1Copy

Copy

One way to make the figure complete is to connect Hole $1$ in Part $1$ and Hole $3$ in Part $3$ and then connect Hole $1$ in Part $2$ and Hole $1$ in Part $3$ .

Sample Input 2Copy

Copy

3
1 1 1

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

6
7 3 5 10 6 4

Sample Output 3Copy

Copy

389183858

Sample Input 4Copy

Copy

9
425656 453453 4320 1231 9582 54336 31435436 14342 423543

Sample Output 4Copy

Copy

667877982