Line++

题目描述

有一个具有 $N$ 个顶点、编号为 $1$ 到 $N$ 的无向图 $G$。$G$ 中共有以下 $N$ 条边:

• 对于 $i=1,2,...,N-1$,顶点 $i$ 和顶点 $i+1$ 之间有边。
• 顶点 $X$ 和顶点 $Y$ 之间有边。

对于 $k=1,2,...,N-1$,请解决以下问题:

• 求满足 $1 \leq i \lt j \leq N$ 的整数对 $(i,j)$,且 $G$ 中顶点 $i$ 到顶点 $j$ 的最短距离为 $k$ 的个数。

输入格式

输入按以下格式从标准输入给出:

$N$ $X$ $Y$

输出格式

对于 $k=1,2,...,N-1$,将问题的答案按顺序每行输出一个。

样例

5 2 4

5
4
1
0

该输入中的图如下所示。

距离为 $1$ 的整数对 $(i,j)$ ($1 \leq i \lt j \leq N$) 有

$(1,2)\,,(2,3)\,,(2,4)\,,(3,4)\,,(4,5)$ 这 $5$ 个。

距离为 $2$ 的整数对 $(i,j)$ ($1 \leq i \lt j \leq N$) 有

$(1,3)\,,(1,4)\,,(2,5)\,,(3,5)$ 这 $4$ 个。

距离为 $3$ 的整数对 $(i,j)$ ($1 \leq i \lt j \leq N$) 有

$(1,5)$ 这 $1$ 个。

距离为 $4$ 的整数对 $(i,j)$ ($1 \leq i \lt j \leq N$) 不存在。

3 1 3

3
0

该输入中的图如下所示。

7 3 7

7
8
4
2
0
0

10 4 8

10
12
10
8
4
1
0
0
0

数据范围

• $3 \leq N \leq 2 \times 10^3$
• $1 \leq X,Y \leq N$
• $X+1 \lt Y$
• 输入均为整数