## Google Code Jam '22 Round 1C Problem C - Intranets

View as PDF

Points: 17 (partial)
Time limit: 60.0s
Memory limit: 1G

Problem types

Apricot Rules LLC is developing a new simplified networking protocol and wants to show off their routing algorithm. In their design, a network consists of machines numbered from to , and each pair of machines is connected by a direct link. Each of the links is given a unique integer priority value between and and each machine routes traffic according to those priorities.

Unfortunately, the routing algorithm is too aggressive and will route all traffic from a machine through the highest priority link connected to it. This may make some groups of machines isolated from others.

Formally, we say that a machine uses a link if (and only if) is the highest priority link connected to . We also say that a link is active if it is used by at least one of the two machines it connects. Given the link priorities, the original network becomes partitioned into disjoint intranets. Two machines belong to the same intranet if and only if there is some path between them using only active links.

For example, as seen in the left image above, only the links with priorities and are active. This creates two disjoint intranets. However, in the example on the right, three links are active, which results in one intranet consisting of all machines.

As part of the quality assurance team at Apricot Rules LLC, you are investigating the extent of the problem. You are interested in knowing the probability of there being exactly intranets if the priorities are assigned uniformly at random from among the ways of doing so.

#### Input Specification

The first line of the input gives the number of test cases, . test cases follow. Each test case is described in a single line containing two integers and : the number of machines and the target number of intranets, respectively.

#### Output Specification

For each test case, output one line containing Case #x: y, where is the test case number (starting from ) and is the sought probability computed modulo the prime , which is defined precisely as follows. Represent the probability as as an irreducible fraction (with and being non-negative integers that minimize ). Then, must equal , where is the modular multiplicative inverse of with respect to the modulus . It can be shown that under the constraints of this problem, such a number always exists and is unique.

#### Limits

.

.

Test Set 1

Time limit: 20 seconds.

.

Test Set 2

Time limit: 60 seconds.

.

#### Sample Input

3
5 2
5 1
6 3

#### Sample Output

Case #1: 428571432
Case #2: 571428576
Case #3: 47619048

#### Explanation for Sample

In Sample Case #1, consider the following situation. Let's call machines and denote the link connecting machine and machine by . Assume that the priorities of links are , respectively. Then machines and use link , machine uses link , and machines and use link . Thus three links are active, and there are two intranets and . Since , this situation counts the answer.

We can find that there are ways to assign the priorities to have exactly intranets among ways, so the probability is .

In Sample Case #2, the probability is .

In Sample Case #3, the probability is .

#### Note

This problem has different time limits for different batches. If you exceed the Time Limit for any batch, the judge will incorrectly display >60.000s regardless of the actual time taken. Refer to the Limits section for batch-specific time limits.