Sequence Slicing

gistfile1.txt

Sequence Slicing

https://www.facebook.com/hackercup/problems.php?pid=317343604974808&round=154897681286317

Let S be a sequence of N natural numbers. We can define an infinite sequence MS in the
following way: MS[k] = S[k mod N] + N * floor(k / N). Where k is a zero based index.

For example if the sequence S is {2, 1, 3} then MS would be {2, 1, 3, 5, 4, 6, 8, 7, 9,
11, 10, 12...}

Now consider a subsequence of MS generated by picking two random indices a, b from the
range [0..R] inclusive, and taking all the elements between them, that is: MS[min(a, b)
..max(a, b)].

If we use the same MS as in the example above and a = 2, b = 5 then our subsequence
would be {3, 5, 4, 6}.

Your task is to calculate the probability that the selected subsequence has at least K
distinct elements. a and b are selected independently and with a uniform distribution.
The result should be printed as a fraction. See the "Output" section for clarification.

Input

The first line of the input file contains an integer T. This is followed by T test
cases, each of which has two lines.

The first line of each test case contains three integers separated by spaces, N, K,
and R.

The second line contains N space separated integers, S[0] through S[N-1].

Constraints

1 ≤ T ≤ 20
1 ≤ N ≤ 2,000;
1 ≤ K ≤ R ≤ 1,000,000,000
1 ≤ S[i] ≤ 100,000

Output

For each of the test cases numbered in order from 1 to T, output "Case #i: " followed
by the probability that the selected subsequence of MS has at least K distinct
elements. The probability should be expressed as a fraction p/q, where p and q
represent the numerator and denominator respectively and are relatively prime (that is
they share no common positive divisors except 1).

If the probability is 0 or 1 output 0/1 or 1/1 respectively.

Examples

In the first example there are 36 different subsequences to consider. 6 of them have
only a single number, and the remaining 30 have at least 2 different numbers, so the
answer is 5/6.

The second example is similar, but now the sequence looks like {2, 1, 5, 5, 4, 8}.
There are 8 subsequences with less than 2 distinct numbers: the six single number
subsequences plus (a=2, b=3) and (a=3, b=2) which both result in {5,5}. That gives a
probability of (36 - 8) / 36 = 7/9.

The third example uses the same sequence as the second example, but now we want to
have subsequences with at least 4 different numbers. All pairs of indices that have
this property are: (0,4), (0, 5), (1, 5), (4, 0), (5, 0), and (5, 1). Six out of
thirty six results in a probability of 1/6.

Example input

5
3 2 5
2 1 3
3 2 5
2 1 5
3 4 5
2 1 5
3 5 5
2 2 5
10 1000 1000000
1 2 3 4 5 6 7 8 9 10

Example output

Case #1: 5/6
Case #2: 7/9
Case #3: 1/6
Case #4: 0/1
Case #5: 998005995006/1000002000001