Preparing NOJ

Rikka with Quicksort

3000ms 524288K

Description:

Rikka is interested in computer science, and she has been practicing coding for two years and a half. Today, she wants to do a simple summary of the algorithms she has learned.

One of the most important algorithms is Quicksort. Though its idea is quite simple, Rikka remembers that it took her a while to prove the time complexity. Let $$$f(n)$$$ be the expected number of comparisons required by Quicksort on a sequence with length $$$n$$$. Then $$$f(n)$$$ follows the following equations:
$$$$$$
\begin{aligned}
f(0) &= 0 \\
f(i) &= i-1 + \frac{1}{i}\sum_{j=1}^{i}\left( f(j-1) + f(i-j)\right) & i \geq 1
\end{aligned}
$$$$$$
After some simple derivations, Rikka finishes the proof and obtains the result that $$$f(n) = O(n \log n)$$$: As an outstanding undergraduate student, this problem is just a piece of cake for her.

To make the task more challenging, Rikka asks Yuta, her boyfriend, to set several exercises for her. The following is the hardest one of them:

Consider a modified version of Quicksort: the recursive process terminates once the length of the interval is less than $$$m$$$. At this time, the expected number of comparisons $$$g_m(n)$$$ can be described with the following equations:
$$$$$$
\begin{aligned}
g_m(i) &= 0 & 0 \leq i \leq m\\
g_m(i) &= i-1 + \frac{1}{i}\sum_{j=1}^{i}\left( g_m(j-1) + g_m(i-j)\right) & i > m
\end{aligned}
$$$$$$
Now, Yuta shows the value of $$$n,m$$$, and he wants Rikka to calculate $$$g_m(n)$$$. It is generally known that Rikka is not good at math. Therefore she wants you to help her calculate the answer.

Input:

The first line is an integer $$$t(1 \leq t \leq 10)$$$, the number of test cases.

For each test case, the input contains a single line with two positive integers $$$n,m(1 \leq m \leq n \leq 10^9)$$$.

Output:

For each test case, output a single line with a single number, the value of $$$g_m(n)$$$.

Clearly, $$$g_m(n)$$$ is a rational number. Therefore, you are required to print $$$g_m(n)\ \text{mod}\ 1000000007$$$, i.e., print $$$x \times y^{-1}\ \text{mod}\ 1000000007$$$ where $$$\frac{x}{y}$$$ is the irreducible fraction representation of $$$g_m(n)$$$.

Sample Input:

5
3 1
5 1
5 3
10 5
1000 500

Sample Output:

666666674
800000013
400000008
308730177
3107840

Info

HDU

Provider HDU

Origin HDU856-1001

Code HDU6680

Tags

Submitted 2

Passed 1

AC Rate 50%

Date 08/19/2019 12:05:19

Related

Nothing Yet