Intranets Solution Round 1C 2022 - Code Jam 2022

Intranets Solution Round 1C 2022 - Code Jam 2022

Problem

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 M$M$ machines numbered from 1$1$ to N$N$, and each pair of machines is connected by a direct link. Each of the links is given a unique integer priority value between 1$1$ and (M×(M−1)/2)$(\mathbf{M}\times (\mathbf{M}-1)/2)$ 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 m$m$ uses a link ℓ$\ell$ if (and only if) ℓ$\ell$ is the highest priority link connected to m$m$. 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 6$6$ and 5$5$ 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 4$4$ machines.

Solution Click Below:- 

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 K$K$ intranets if the priorities are assigned uniformly at random from among the (M×(M−1)/2)!$(\mathbf{M}\times (\mathbf{M}-1)/2)!$ ways of doing so.

Input

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

Letter Blocks Solution Round 1C 2022 - Code Jam 2022

Squary Solution Round 1C 2022 - Code Jam 2022

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is the sought probability computed modulo the prime 109+7${10}^9+7$ (1000000007$1000000007$), which is defined precisely as follows. Represent the probability as as an irreducible fraction p/q$p/q$ (with p$p$ and q$q$ being non-negative integers that minimize p+q$p+q$). Then, y$y$ must equal p⋅q−1mod109+7$p\cdot q^{-1}mod{10}^9+7$⁠, where q−1$q^{-1}$ is the modular multiplicative inverse of q$q$ with respect to the modulus 109+7${10}^9+7$. It can be shown that under the constraints of this problem, such a number y$y$ always exists and is unique.

Limits

Memory limit: 1 GB.
1≤T≤50$1\le \mathbf{T}\le 50$.
1≤K≤M/2$1\le \mathbf{K}\le \mathbf{M}/2$.

Test Set 1 (Visible Verdict)

Time limit: 20 seconds.
2≤M≤50$2\le \mathbf{M}\le 50$.

Test Set 2 (Hidden Verdict)

Time limit: 60 seconds.
2≤M≤5×105$2\le \mathbf{M}\le 5\times {10}^5$.

Sample

Sample Input

3
5 2
5 1
6 3

Sample Output

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

In Sample Case #1, consider the following situation. Let's call M=5$\mathbf{M}=5$ machines 1,2,3,4,5$1,2,3,4,5$ and denote the link connecting machine a$a$ and machine b$b$ by (a,b)$(a,b)$. Assume that the priorities of links (1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)$(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)$ are 9,8,7,6,5,4,3,2,1,10$9,8,7,6,5,4,3,2,1,10$, respectively. Then machines 1$1$ and 2$2$ use link (1,2)$(1,2)$, machine 3$3$ uses link (1,3)$(1,3)$, and machines 4$4$ and 5$5$ use link (4,5)$(4,5)$. Thus three links (1,2),(1,3),(4,5)$(1,2),(1,3),(4,5)$ are active, and there are two intranets {1,2,3}$\{1,2,3\}$ and {4,5}$\{4,5\}$. Since K=2$\mathbf{K}=2$, this situation counts the answer.

We can find that there are 1555200$1555200$ ways to assign the priorities to have exactly 2$2$ intranets among 10!=3628800$10!=3628800$ ways, so the probability is 3/7$3/7$.

In Sample Case #2, the probability is 4/7$4/7$.

In Sample Case #3, the probability is 1/21$1/21$.