Line++

题目描述

我们有一个无向图 $G$，有 $N$ 个按 $1$ 到 $N$ 编号的顶点，以及如下 $N$ 条边：

对于每个 $i=1,2,...,N-1$，在顶点 $i$ 与顶点 $i+1$ 之间有一条边。 在顶点 $X$ 与顶点 $Y$ 之间有一条边。

对于每个 $k=1,2,...,N-1$，求解下面的问题：

找出满足最短距离为 $k$ 的整数对 (i,j) (1 \leq i < j \leq N) 的数量。

输入格式

输入从标准输入按以下格式给出： $N$ $X$ $Y$

输出格式

对于每个 $k=1, 2, ..., N-1$（按此顺序），输出一行包含问题的答案。

5 2 4

5
4
1
0

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 < Y 输入中的所有数值均为整数。该输入对应的图如下：



对于最短距离为 $1$ 的所有 (i,j) (1 \leq i < j \leq N)，共有五个对：$(1,2)\,,(2,3)\,,(2,4)\,,(3,4)\,,(4,5)$。
对于最短距离为 $2$ 的所有 (i,j) (1 \leq i < j \leq N)，共有四个对：$(1,3)\,,(1,4)\,,(2,5)\,,(3,5)$。
对于最短距离为 $3$ 的所有 (i,j) (1 \leq i < j \leq N)，有一个对：$(1,5)$。
对于最短距离为 $4$ 的所有 (i,j) (1 \leq i < j \leq N)，没有任何对。
The graph in this input is as follows:

标签: AtCoder|abc160D

来源

AtCoder|abc160D