3543. 夜游 ECNU

单点时限: 2.0 sec

内存限制: 256 MB

ultmaster 男神带着小迷妹们夜游 ECNU 闵大荒校区,他从学校西南门即原点 $(0, 0)$ 出发前往 ECNU 各个景点。

由于 ultmaster 是个大懒虫,因此他们只会沿着最短路走(即只能往北或者东走,不一定沿着格线)。由于 ECNU 实在是太大太无聊,他们希望在路线是最短路的前提下,在路上还能途径一些景点。两条路线是不同的,当且仅当他们途径的景点不同。无聊的 ultmaster 想知道他们能走出多少条不同的路线。由于答案可能很大,故对 $10^9+7$ 取模。

输入格式

第一行一个整数 $n$ $(1 \leq n \leq 10^5)$ 表示不同的景点个数。

之后 $n$ 行,每行两个整数 $x_i,y_i$ $(0 \leq x_i,y_i \leq 10^9)$ 表示景点的坐标。

保证景点位置各不相同,且不为原点。

输出格式

一行 $n$ 个整数 $c_1,c_2,\ldots,c_n$ 以空格隔开,表示以每个景点为终点不同的游览路线数。

样例

Input
2
1 1
2 2
Output
1 2
Input
3
1 2
2 1
3 3
Output
1 1 3

提示

样例二:到达 3 号景点可以直接从起点出发到达、经过 1 号景点或者经过 2 号景点三种方案。注意不能经过 1 再经过 2 再到 3,因为这不是最短路径。

47 人解决,69 人已尝试。

56 份提交通过,共有 289 份提交。

4.7 EMB 奖励。

创建: 6 年,6 月前.

修改: 6 年,5 月前.

最后提交: 1 年前.

来源: EOJ Monthly 2018.4

题目标签
DP