F - Maximum Diameter Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

長さ N の正整数列 X=(X_1,X_2\ldots,X_N) に対して、f(X) を以下のように定めます。

  • N 頂点の木であって、i\ (1 \leq i \leq N) 番目の頂点の次数が X_i であるようなものを良い木と呼ぶ。 良い木が存在するならば、f(X) は良い木の直径の最大値。良い木が存在しないならば、f(X)=0。

ただし、木の 2 頂点の間の距離は一方から他方へ移動するときに用いる辺の本数の最小値であり、 木の直径は任意の 2 頂点の間の距離の最大値として定められます。

長さ N の正整数列 X としてあり得るもの全てに対する f(X) の総和を 998244353 で割った余りを求めてください。 なお、f(X) の総和は有限値になることが証明できます。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1\leq T \leq 2\times 10^5
  • 2 \leq N \leq 10^6
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで、\mathrm{test}_i は i 番目のテストケースを意味する。

T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T

各テストケースは以下の形式で与えられる。

N

出力

T 行出力せよ。

i\ (1\leq i \leq T) 行目には、i 番目のテストケースに対する答えを出力せよ。

入力例 1

10
2
3
5
8
13
21
34
55
89
144

出力例 1

1
6
110
8052
9758476
421903645
377386885
881422708
120024839
351256142

N=3 の場合について、

例えば、

  • X=(1,1,1) のとき、次数が 1,1,1 となる 3 頂点の木は存在しないため、f(X)=0 です。
  • X=(2,1,1) のとき、良い木は以下の図のものに限られます。この木の直径は 2 であるため、f(X)=2 です。


3 頂点の木

X=(2,1,1),(1,2,1),(1,1,2) のとき f(X)=2 であり、それ以外の X のとき f(X)=0 であるため、答えは 6 です。

Score : 500 points

Problem Statement

For a sequence X=(X_1,X_2\ldots,X_N) of length N consisting of positive integers, we define f(X) as follows:

  • A tree with N vertices is said to be good if and only if the degree of the i-th (1 \leq i \leq N) vertex is X_i. If a good tree exists, f(X) is the maximum diameter of a good tree; if it doesn't, f(X)=0.

Here, the distance between two vertices is the minimum number of edges that must be traversed to travel from one vertex to the other, and the diameter of a tree is the maximum distance between two vertices.

Find the sum, modulo 998244353, of f(X) over all possible sequences X of length N consisting of positive integers. We can prove that the sum of f(X) is a finite value.

Given T test cases, find the answer for each of them.

Constraints

  • 1\leq T \leq 2\times 10^5
  • 2 \leq N \leq 10^6
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{test}_i denotes the i-th test case:

T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T

Each test case is given in the following format:

N

Output

Print T lines.

The i-th (1\leq i \leq T) line should contain the answer to the i-th test case.

Sample Input 1

10
2
3
5
8
13
21
34
55
89
144

Sample Output 1

1
6
110
8052
9758476
421903645
377386885
881422708
120024839
351256142

If N=3,

for example,

  • when X=(1,1,1), there is no tree with three vertices whose degrees are 1,1, and 1, so f(X)=0.
  • When X=(2,1,1), the only possible tree is illustrated below. The diameter of this tree is 2, so f(X)=2.


3-vertex tree

For X=(2,1,1),(1,2,1),(1,1,2), we have f(X)=2; for other X, we have f(X)=0. Thus, the answer is 6.