AT_abc290_f [ABC290F] Maximum Diameter

题目描述

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

• 如果存在一棵有 $N$ 个顶点的树，且第 $i$ 个顶点的度数为 $X_i$，则称这棵树为“好树”。若存在好树，则 $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$ 行输出第 $i$ 组测试数据的答案。

输入输出样例 #1

输入 #1

10
2
3
5
8
13
21
34
55
89
144

输出 #1

1
6
110
8052
9758476
421903645
377386885
881422708
120024839
351256142

说明/提示

数据范围

• $1 \leq T \leq 2 \times 10^5$
• $2 \leq N \leq 10^6$
• 输入均为整数

样例解释 1

以 $N=3$ 为例：

• $X=(1,1,1)$ 时，不存在度数为 $1,1,1$ 的 $3$ 个顶点的树，因此 $f(X)=0$。
• $X=(2,1,1)$ 时，唯一的好树如下图所示，其直径为 $2$，因此 $f(X)=2$。

对于 $X=(2,1,1),(1,2,1),(1,1,2)$，$f(X)=2$，其余情况 $f(X)=0$，因此答案为 $6$。

由 ChatGPT 4.1 翻译