|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||512 MB||11||7||6||66.667%|
You run a hotel with N rooms arranged along one long corridor, numbered from 1 to Nalong that corridor. Your guests are big families, and every family asks for exactly two adjacent rooms when they arrive. Two rooms are adjacent if their numbers differ by exactly 1.
At the start of the day today, your hotel was empty. You have been using the following simple strategy to assign rooms to your guests. As each family arrives, you consider all possible pairs of adjacent rooms that are both free, pick one of those pairs uniformly at random, and assign the two rooms in that pair to the family. New families constantly arrive, one family at a time, but once there are no more pairs of adjacent rooms that are both free, you turn on the NO VACANCY sign and you do not give out any more rooms.
Given a specific room number, what is the probability that it will be occupied at the time that you turn on the NO VACANCY sign?
The first line of the input gives the number of test cases, T. T lines follow. Each line contains two numbers: the number of rooms N and the room number K that we are interested in.
For each test case, output one line containing
Case #x: y, where
x is the test case number (starting from 1) and
y is the sought probability computed modulo 109+7, which is defined precisely as follows. Represent the probability that room K is occupied as an irreducible fraction
p/q. The number
y then must satisfy the modular equation
y × q ≡ p (mod 109+7), and be between 0 and 109+6, inclusive. It can be shown that under the constraints of this problem such a number
y always exists and is uniquely determined.
4 3 1 3 2 4 1 4 2
Case #1: 500000004 Case #2: 1 Case #3: 666666672 Case #4: 1
In sample case #3, there are four rooms and we are looking for probability that the first room is occupied. When the first family arrives, there are 3 possible situations, each with probability 1/3: occupy rooms 1+2, 2+3 or 3+4. In the first situation, the first room is already occupied and will stay occupied. In the second situation, the first room is free and no more families can be accommodated, so it will stay free. Finally, in the third situation, the next arriving family will definitely get rooms 1+2, and thus the first room will be occupied. The probability that the first room is occupied is thus 2/3, and the answer is 666666672, since
(666666672 * 3) mod 1000000007 = 2 mod 1000000007.
The probability for sample case #1 is 1/2, and for sample cases #2 and #4 it is 1.