分数: 400 点
问题陈述
我们有一个无向图 G 与 N 顶点编号 1 to N 和 N 边缘如下:
- 对于每个 i=1,2,...,N-1,顶点之间有一条边 i 和顶点 i+1.
- 顶点之间有一条边 X 和顶点 Y.
对于每个 k=1,2,...,N-1,解决以下问题:
- 查找整数对的数量 (i,j) (1 \leq i < j \leq N) 使得顶点之间的最短距离 i 和顶点 j in G is k.
约束
- 3 \leq N \leq 2 \times 10^3
- 1 \leq X,Y \leq N
- X+1 < Y
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N X Y
输出
对于每个 k=1, 2, ..., N-1 按照此顺序,打印包含问题答案的行。
示例输入 1
5 2 4
示例输出 1
5 4 1 0
该输入中的图表如下:
有五对 (i,j) (1 \leq i < j \leq N) 使得顶点之间的最短距离 i 和顶点 j is 1: (1,2)\,,(2,3)\,,(2,4)\,,(3,4)\,,(4,5).
有四对 (i,j) (1 \leq i < j \leq N) 使得顶点之间的最短距离 i 和顶点 j is 2: (1,3)\,,(1,4)\,,(2,5)\,,(3,5).
有一对 (i,j) (1 \leq i < j \leq N) 使得顶点之间的最短距离 i 和顶点 j is 3: (1,5).
没有对 (i,j) (1 \leq i < j \leq N) 使得顶点之间的最短距离 i 和顶点 j is 4.
示例输入 2
3 1 3
示例输出 2
3 0
该输入中的图表如下:
示例输入 3
7 3 7
示例输出 3
7 8 4 2 0 0
示例输入 4
10 4 8
示例输出 4
10 12 10 8 4 1 0 0 0