作者： chenchen

Farmer John has N cows on his farm (2≤N≤2⋅10⁵), conveniently numbered 1…N
. Cow i is located at integer coordinates (x_i,y_i) (1≤x_i,y_i≤N). Farmer John wants to pick two teams for a game of mooball!

One of the teams will be the "red" team; the other team will be the "blue" team. There are only a few requirements for the teams. Neither team can be empty, and each of the N cows must be on at most one team (possibly neither). The only other requirement is due to a unique feature of mooball: an infinitely long net, which must be placed as either a horizontal or vertical line in the plane at a non-integer coordinate, such as x=0.5. FJ must pick teams so that it is possible to separate the teams by a net. The cows are unwilling to move to make this true.

Help a farmer out! Compute for Farmer John the number of ways to pick a red team and a blue team satisfying the above requirements, modulo 10⁹+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains a single integer N.

The next N lines of input each contain two space-separated integers x_i and y_i. It is guaranteed that the x_i form a permutation of 1…N, and same for the y_i.

OUTPUT FORMAT (print output to the terminal / stdout):

A single integer denoting the number of ways to pick a red team and a blue team satisfying the above requirements, modulo 10⁹+7.

SAMPLE INPUT:
2
1 2
2 1

SAMPLE OUTPUT:
2
We can either choose the red team to be cow 1 and the blue team to be cow 2, or the other way around. In either case, we can separate the two teams by a net (for example, x=1.5).

SAMPLE INPUT:

3
1 1
2 2
3 3

SAMPLE OUTPUT:

10

Here are all ten possible ways to place the cows on teams; the ith character denotes the team of the ith cow, or . if the ith cow is not on a team.

RRB
R.B
RB.
RBB
.RB
.BR
BRR
BR.
B.R
BBR

SAMPLE INPUT:

3
1 1
2 3
3 2

SAMPLE OUTPUT:

12

Here are all twelve possible ways to place the cows on teams:

RRB
R.B
RBR
RB.
RBB
.RB
.BR
BRR
BR.
BRB
B.R
BBR

SAMPLE INPUT:

40
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40

SAMPLE OUTPUT:

441563023

Make sure to output the answer modulo 109+7.

SCORING:

Input 5: N≤10
Inputs 6-9: N≤200
Inputs 10-13: N≤3000
Inputs 14-24: No additional constraints.
Problem credits: Dhruv Rohatgi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

**Note: The memory limit for this problem is 512MB, twice the default.**

Bessie is having fun playing a famous online game, where there are a bunch of cells of different labels and sizes. Cells get eaten by other cells until only one winner remains.

There are N (2≤N≤5000) cells in a row labeled 1…N from left to right, with initial sizes s₁,s₂,…,s_N (1≤s_i≤10⁵). While there is more than one cell, a pair of adjacent cells is selected uniformly at random and merged into a single new cell according to the following rule:

If a cell with label a and current size c_a is merged with a cell with label b and current size c_b , the resulting cell has size c_a +c_b and label equal to that of the larger cell, breaking ties by larger label. Formally, the label of the resulting cell is

For each label i in the range 1…N , the probability that the final cell has label i
can be expressed in the form where b_i≢0 ( mod 10⁹+7). Output a_ib⁻¹_i ( mod 10⁹+7).

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.
The next line contains s₁,s₂,…,s_N

OUTPUT FORMAT (print output to the terminal / stdout):

The probability of the final cell having label i modulo 10⁹+7
for each i in 1…N on separate lines.

SAMPLE INPUT:

3
1 1 1

SAMPLE OUTPUT:

0
500000004
500000004

There are two possibilities, where (a,b)→c means that the cells with labels a and b merge into a new cell with label c.

(1, 2) -> 2, (2, 3) -> 2
(2, 3) -> 3, (1, 3) -> 3

So with probability 1/2 the final cell has label 2 or 3.

SAMPLE INPUT:

4
3 1 1 1

SAMPLE OUTPUT:

666666672
0
166666668
166666668
The six possibilities are as follows:

(1, 2) -> 1, (1, 3) -> 1, (1, 4) -> 1
(1, 2) -> 1, (3, 4) -> 4, (1, 4) -> 1
(2, 3) -> 3, (1, 3) -> 1, (1, 4) -> 1
(2, 3) -> 3, (3, 4) -> 3, (1, 3) -> 3
(3, 4) -> 4, (2, 4) -> 4, (1, 4) -> 4
(3, 4) -> 4, (1, 2) -> 1, (1, 4) -> 1

So with probability 2/3 the final cell has label 1, and with probability 1/6
the final cell has label 3 or 4.

SCORING:

Input 3: N≤8
Inputs 4-8: N≤100
Inputs 9-14: N≤500
Inputs 15-22: No additional constraints.
Problem credits: Benjamin Q_i

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie is taking a vacation in a network of N(2≤N≤10⁴) islands labeled 1…N
connected by M bidirectional bridges, each of which connects two islands (N−1≤M≤3/2(N−1)). It is guaranteed that the bridges form a connected simple graph (in particular, no two bridges connect the same pair of islands, and no bridge connects an island to itself).

It is also guaranteed that no bridge lies on more than one simple cycle. A simple cycle is a cycle that does not contain repeated islands.

Bessie starts at island 1, and travels according to the following procedure. Supposing she is currently at island i,

1.If there are no bridges adjacent to island i that she has not yet crossed, she ends her vacation.
2.Otherwise, with probability pi(mod 10⁹+7), she ends her vacation.
3.Otherwise, out of all bridges adjacent to island i that she has not yet crossed, she chooses one uniformly at random and crosses it.

For each island, output the probability that she ends her vacation at that island, modulo 10⁹+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains the number of independent test cases T (1≤T≤10). Consecutive test cases are separated by an empty line.

The first line of each test contains N and M, where N is the number of islands and M is the number of bridges. It is guaranteed that the sum of N over all test cases does not exceed 10⁴.

The second line of each test contains p₁,p₂,…,p_N (0≤p_i<10⁹+7).

The next M lines of each test describe the bridges. The ith line contains integers ui and vi (1≤u_i<v_i≤N), meaning that the ith bridge connects islands u_i and v_i. It is guaranteed that the bridges satisfy the constraints mentioned above.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output the probability of ending at each island from 1
to N modulo 10⁹+7 on a single line, separated by spaces.

SAMPLE INPUT:
2

3 2
0 10 111111112
1 3
2 3

6 5
500000004 0 0 0 0 0
1 5
1 3
4 5
5 6
1 2

SAMPLE OUTPUT:

0 888888896 111111112
500000004 166666668 166666668 83333334 0 83333334

For the first test case,p₃≡1/9(mod 10⁹+7). Bessie has probability 1/9
of ending at 3(taking the path 1→3) and 8/9of ending at 2(taking the path 1→3→2).

For the second test case, p₁ ≡1/2(mod 10⁹+7). Bessie has probability 1/2
of ending at 1, 1/6 of ending at each of 2
or 3, and 1/12 of ending at each of 4 or 6.

SAMPLE INPUT:
2

5 5
333333336 333333336 0 0 0
1 2
2 3
3 4
4 5
1 5

5 5
0 0 0 0 0
1 2
2 3
2 4
1 4
1 5

SAMPLE OUTPUT:

777777784 222222224 0 0 0
0 0 333333336 0 666666672

For the first test case, p₁ ≡p₂≡1/3(mod 10⁹+7). Bessie has probability 7/9
of ending at 1 (taking one of the paths 1, 1→2→3→4→5→1, or 1→5→4→3→2→1) and 2/9 of ending at 2.

For the second test case, Bessie has probability 1/3 of ending at 3, and 2/3 of ending at 5.

SAMPLE INPUT:

1

11 13
2 3 4 5 6 7 8 9 10 11 12
1 2
1 3
2 3
2 4
4 5
2 5
4 8
5 9
2 6
6 7
2 7
6 10
5 11

SAMPLE OUTPUT:

133332478 200000394 577778352 999999971 399999938 933333282 355555536 800000020 18 600000029 18

SCORING:

Inputs 4-5: N≤11
Inputs 6-7: There are no simple cycles.
Inputs 8-11: No island lies on more than one simple cycle.
Inputs 12-15: No island lies on more than 5 simple cycles.
Inputs 16-19: No island lies on more than 50 simple cycles.
Inputs 20-23: No additional constraints.

Problem credits: Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

USACO 2024 年 1 月比赛将于 1 月 26 日至 1月 29 开赛，USACO面向全球信息学爱好者免费开放，但只有美国的高中（大学预科）学生有资格获得被选为参加USACO训练营的决赛选手，并代表美国队参加ioi。

技术说明：USACO官网的评审服务器支持C++17，Python 3.6 和 Java 11（Pascal 已在两年前停止）。更多细节可以在比赛规则中找到。强烈建议参与者仔细阅读这些内容，因为它们突出显示了一些我们的主要比赛规则、不允许使用来自外部来源或生成式 AI）。请注意，从上个赛季开始，样本案件不再计入最终得分(它们仍然必须与所有其他案件一起解决)。

比赛分为四个组别：铜牌、银牌、金牌和铂金。所有返回的参与者都从他们的前组别和新参赛者从铜牌开始划分。比赛仅限个人，不适用于团队。

关于白金比赛的注意事项：

对于参加白金级比赛的美国学生，如果您在美国东部时间1月27日星期六12:00至12:15之间开始比赛，您将获得认证分数。认证分数在最终选择中具有更大的权重。这个特殊的计时目前只影响白金比赛。也就是说，白金问题只在美国东部时间1月27日中午可用，而所有其他部门在1月26日上午启动。希望获得参加我们训练营决赛的充分考虑的学生应尽量获得所有白金比赛的认证分数。考虑到时间安排有时很难协调，获得3分而不是4分认证分数的学生仍将得到充分考虑。由于赛季中期从金级提升到白金级，认证分数少于3分的学生也可能被考虑进入决赛(在这种情况下，认证分数越高越好)。

在当前组别中得分特别高的参赛者 将晋升到下一个组别，参加未来的比赛 （晋级标准在比赛结束时公布，并且因每场比赛而异，因为每场比赛都不同）。 在比赛中晋升也是可能的，如果你达到满分。如果你在比赛中得到晋升，你将能够在满时的情况下参加更高级别的比赛(不会因为之前的比赛而受到惩罚)。

每场比赛有3个问题，你需要用C、c++、Java或Python提交解决方案。问题本质上是算法问题，每个问题的得分取决于你的程序在限定时间内能够解决的输入案例的数量(本次比赛:C和c++的每个输入案例2秒，Java和Python的每个输入案例4秒)。如果您的程序正确地解决了示例输入情况(包括在每个问题的文本中)，您将收到关于它如何执行我们的每个判断输入的反馈。例如，您将被告知您的程序是否产生了正确的答案，超时，遇到运行时错误等。请注意，尽管您收到了这些反馈，但除了示例案例之外，其余的裁判输入在比赛期间不会公开。问题要具有挑战性;很少有很多竞争者获得接近完美的分数!

比赛持续4个小时。您可以在1月26日至1月29日的大比赛窗口期间的任何4小时内参加比赛。当你开始比赛时，你的个人4小时计时器开始倒计时，你可以通过这个网站查看比赛问题并提交解决方案。比赛将于1月29日23:59 UTC-12时间结束(即使你的个人时钟还在运行，所以不要等到最后一分钟才开始!)

比赛结果将在比赛结束后不久发布在本网站上。

说明和规则

详细的比赛说明可在此查看。如果你还没有读过，请阅读。请注意，如果您使用Java编程，则需要遵循一些特殊要求(例如，将整个程序提交到一个文件中)，这些要求在说明中有概述。如果您遇到任何技术问题，请给大赛总监发邮件(bcdean@clemson.edu)。

语言可用性

比赛目前有以下语言版本:英语、法语、俄语、俄语、德语、德语(仅限铜牌和银牌)。
更多的翻译可能会在稍后的比赛中提供。