47 人解决,69 人已尝试。
56 份提交通过,共有 289 份提交。
4.7 EMB 奖励。
单点时限: 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$ 以空格隔开,表示以每个景点为终点不同的游览路线数。
2 1 1 2 2
1 2
3 1 2 2 1 3 3
1 1 3
样例二:到达 3 号景点可以直接从起点出发到达、经过 1 号景点或者经过 2 号景点三种方案。注意不能经过 1 再经过 2 再到 3,因为这不是最短路径。
47 人解决,69 人已尝试。
56 份提交通过,共有 289 份提交。
4.7 EMB 奖励。