102905: [Atcoder]ABC290 F - Maximum Diameter
Description
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$.
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$.
Input
题意翻译
对于一个长度为 $n$ 的正整数序列 $X=(X_1,X_2,\cdots,X_n)$,定义 $f(X)$ 为: - 对于所有节点数量为 $n$,且点 $i$ 的度数恰好为 $X_i$ 的树,其直径的最大值。如不存在,则值为 $0$。 你需要对于所有长度为 $n$ 的正整数序列 $X$ 计算 $f(X)$ 的和,可以证明其为有限值。答案对 $998244353$ 取模。 $T$ 组数据。$1\le T\le2\times10^5$,$2\le n\le10^6$。 —— by Register_intOutput
分数:500分
问题描述
对于长度为$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$。
这里,两个顶点之间的距离是从一个顶点到另一个顶点必须经过的最少边数,树的直径是两个顶点之间的最大距离。
求所有可能的正整数序列$X$的长度为$N$的$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$的树,所以$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$。