COOLPROB - Cool Problem

no tags 

Prem Kamal went to Tokyo, where one day he decided to tour the city. He will be visiting a number of regions. In each region, there are N buildings of heights H1,H2...HN.
A region is represtented across x-axis with buildings placed at positions 1..N, next to each other in a random order (let the order be represented as h1,h2...hN).
Prem Kamal, known for his cool acts, decides to calculate the coolness of the region. Each position has some coolness score (C(i)) associated with it. But that coolness score is added only if there is a cool building at that position. A building is cool if it is strictly taller than its left and right neighbor (first and last buildings are not considered cool). Moreover, since it gets boring going through the same region, the coolness score of later positions is lesser. See the formal definitions carefully.

Formal Definitions:
C(1) = 1
C(i) = C(i-1)*0.99
The heights Hi are generated as follows:
H1 = X
Hi = (Hi-1 * X) mod 10007

Given N and X, what is the expected overall coolness of the region.

Constraints
T = 2000
1<=N<=10^3
2<=X<=10^3

Input
First line consists of the number of test cases T. T test cases follow. Each test cases consist of a space separated integers N and X.

Output
For each teste case, print the expected overall coolness score of the region. Round the results and print exactly 6 decimal places. ('%.6lf' format specifier for double in C)

Sample Input
2
3 3
2 10
Sample Output
0.330000
0.000000

Explanation

For first sample case, the heights are (3, 9, 27) and position scores are (1, 0.99, 0.99*0.99)
However there are only two possible configurations out of 6 where there exists a cool building.
Coolness of (3, 27, 9) = 0.99  (there is a cool building at position 2)
Coolness of (9, 27, 3) = 0.99
Expected coolness = 0.99*1/6 + 0.99*1/6 = 0.33


hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2015-02-25 04:52:14

Amazing problem, there are many ways/approach to solve this problem, and one of them is very funny math, just like my AVMG1 ;-)


Added by:VV
Date:2015-01-28
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Own problem (CQM 7, BIT Mesra)