NC14365. Expected Waiting Time
描述
DreamGrid is a famous coach of competitive programming. He is so kind that many competitors are willing to ask him for advice.
DreamGrid meets exactly n competitors every day in his office, and thus n "arriving" events and n "selecting" events will happen. An arriving event at time t indicates that a competitor arrives at the waiting room of the office at time t , and a selecting event at time t indicates that DreamGrid randomly selects (with equal probability) a competitor from the waiting room to talk with. Of course, if the selecting event happens, the waiting room must not be empty. After the talk, the competitor leaves the office and never comes back.
After several days, DreamGrid starts to be curious about the average of the total expected waiting time of every competitor in all valid cases. The waiting time of a competitor is the time he is selected by DreamGrid minus the time he arrives at the waiting room. A case is a sequence of length 2n consisting of n arriving events and n selecting events, where the i -th event will happen at time ai . For a valid case, it must be satisfied that when a selecting event happens, the waiting room must not be empty.
For example, let's denote an arriving event as 'A', and a selecting event as 'S'. If n = 2,a1 = 1,a2 = 2,a3 = 3, and a4 = 4, then the sequence "AASS" is valid, but the sequence "ASSA" is not valid, as the "selecting" event happening at time a3 = 3 is not valid.
As the answer may not be an integer, you are supposed to calculate ab-1 mod p , where
( a and b are coprime) is the answer, p > 2n and is p prime, and is the modular multiplicative inverse b of with respect to the modulus p. It's easy to prove that the prime factors of b will never be larger than 2n.
( a and b are coprime) is the answer, p > 2n and is p prime, and is the modular multiplicative inverse b of with respect to the modulus p. It's easy to prove that the prime factors of b will never be larger than 2n. 输入描述
There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 104), indicating the number of test cases. For each test case:The first linecontains five integersn, p ,b0 ,A ,B (1 ≤ n ≤ 106,2n < p ≤ 2×109, 0 ≤ b0, A ,B < p), where p is aprime number. The meanings ofn andp are described above. The rest of them is agenerator of a, where a0 = 0, ai = ai-1 + bi + 1 and bi = (A ⋅ bi−1 + B) mod p for all 1 ≤ i ≤ 2n.It is guaranteed that the sum of n in all test cases does not exceed 107.
输出描述
For each test case, output one integer denoting the answer in a single line.
示例1
输入:
5 1 1000000007 0 1 0 2 1000000007 0 1 1 2 7 5 2 3 3 31 15 6 24 20 1000000007 0 1 0
输出:
1 12 1 21 879705565
说明:
Let's denote the arriving event as 'A', and the selecting event as 'S'.
In the first test case, we have a1 = 1 and a2 = 2,and there is only one valid sequence "AS". The waiting time of the only competitor is 2-1 = 1, so the answer is 1, and we need to output 1 mod 1000000007 = 1.
In the second test case, we have In the second test case, we have ,a2 = 5 , a3 = 9 and a4 = 14. There are two valid sequences "ASAS" and "AASS".
For the first sequence, the expected waiting time of the first arriving competitor is 5-2 = 3, and the expected waiting time of the second arriving competitor is 14-9 = 5.
For the second sequence, the expected waiting time of the first arriving competitor is ((9-2)+(14-2))/2 = 9.5, and the expected waiting time of the second arriving competitor is ((9-5)+(14-5))/2 = 6.5. So the answer is ((3+5)+(9.5+6.5))/2 = 12, and we need to output 12 mod 1000000007 = 12.