Maximum Diameter

题目描述

对于长度为 $N$ 且由正整数组成的序列 $X=(X_1,X_2\ldots,X_N)$，我们定义 $f(X)$ 如下：

当且仅当第 $i$ 个 $(1 \leq i \leq N)$ 顶点的度数为 $X_i$ 时，该有 $N$ 个顶点的无向树称为良好树。 如果存在良好树，则 $f(X)$ 为所有良好树的最大直径；如果不存在，则 $f(X)=0$。

这里，两个顶点之间的距离是从一个顶点到另一个顶点所需经过的最少边数，树的直径是两个顶点之间距离的最大值。 求在所有可能的长度为 $N$ 且由正整数组成的序列 $X$ 上 $f(X)$ 的和，对 $998244353$ 取模。 可以证明 $f(X)$ 的和是有限的。 给定 $T$ 个测试用例，求每个测试用例的答案。

输入格式

输入从标准输入给出，格式如下，其中 $\mathrm{test}_i$ 表示第 $i$ 个测试用例： $T$ $\mathrm{test}_1$ $\mathrm{test}_2$ \vdots $\mathrm{test}_T$

每个测试用例按如下格式给出： $N$

输出格式

输出 $T$ 行。 第 $i$ 行 $(1\leq i \leq T)$ 应包含第 $i$ 个测试用例的答案。

10
2
3
5
8
13
21
34
55
89
144

1
6
110
8052
9758476
421903645
377386885
881422708
120024839
351256142

提示

$1\leq T \leq 2\times 10^5$ $2 \leq N \leq 10^6$ 输入中的所有数值均为整数。例如当 $N=3$ 时，

当 $X=(1,1,1)$ 时，不存在三个顶点的树，其度数分别为 $1,1,1$，因此 $f(X)=0$。 当 $X=(2,1,1)$ 时，唯一可能的树如下所示。该树的直径为 $2$，所以 $f(X)=2$。

对于 $X=(2,1,1),(1,2,1),(1,1,2)$，我们有 $f(X)=2$；对于其他 $X$，我们有 $f(X)=0$。因此答案为 $6$。

标签: AtCoder|abc290F

来源

AtCoder|abc290F