← 返回题目列表

AtCoder · abc290_f

I. 最大直径

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

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

  • 一棵树 N 顶点被认为是好的当且仅当 i-th (1 \leq i \leq N) 顶点是 X_i。 如果存在一棵好树, f(X) 是好树的最大直径;如果没有的话 f(X)=0.

这里,两个顶点之间的距离是从一个顶点到另一个顶点必须遍历的最小边数, 树的直径是两个顶点之间的最大距离。

求总和,取模 998244353,属于 f(X) 所有可能的序列 X 长度 N 由正整数组成。 我们可以证明总和 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-th (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

If N=3,

例如,

  • 当 分别是 X=(1,1,1),不存在度数为 3 个顶点的树 1,1,和 1,所以 f(X)=0.
  • 当 X=(2,1,1),唯一可能的树如下所示。 这棵树的直径是 2,所以 f(X)=2.


3-vertex tree

对于 X=(2,1,1),(1,2,1),(1,1,2),我们有 f(X)=2;对于其他 X,我们有 f(X)=0。 因此,答案是 6.