G. El Toll Caves

Codeforces

IDCF868G

Time2000ms

Memory256MB

Difficulty—

math

English · Original

Chinese · Translation

Formal · Original

The prehistoric caves of El Toll are located in Moià (Barcelona). You have heard that there is a treasure hidden in one of _n_ possible spots in the caves. You assume that each of the spots has probability 1 / _n_ to contain a treasure. You cannot get into the caves yourself, so you have constructed a robot that can search the caves for treasure. Each day you can instruct the robot to visit exactly _k_ distinct spots in the caves. If none of these spots contain treasure, then the robot will obviously return with empty hands. However, the caves are dark, and the robot may miss the treasure even when visiting the right spot. Formally, if one of the visited spots does contain a treasure, the robot will obtain it with probability 1 / 2, otherwise it will return empty. Each time the robot searches the spot with the treasure, his success probability is independent of all previous tries (that is, the probability to miss the treasure after searching the right spot _x_ times is 1 / 2_x_). What is the expected number of days it will take to obtain the treasure if you choose optimal scheduling for the robot? Output the answer as a rational number modulo 109 + 7. Formally, let the answer be an irreducible fraction _P_ / _Q_, then you have to output . It is guaranteed that _Q_ is not divisible by 109 + 7. ## Input The first line contains the number of test cases _T_ (1 ≤ _T_ ≤ 1000). Each of the next _T_ lines contains two integers _n_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 5·108). ## Output For each test case output the answer in a separate line. [samples] ## Note In the first case the robot will repeatedly search in the only spot. The expected number of days in this case is 2. Note that in spite of the fact that we know the treasure spot from the start, the robot still has to search there until he succesfully recovers the treasure. In the second case the answer can be shown to be equal to 7 / 2 if we search the two spots alternatively. In the third case the answer is 25 / 9.

El Toll 的史前洞穴位于莫亚（巴塞罗那）。你听说宝藏隐藏在洞穴中的 #cf_span[n] 个可能位置之一。你假设每个位置包含宝藏的概率均为 #cf_span[1 / n]。你无法亲自进入洞穴，因此你制造了一台机器人来搜索洞穴中的宝藏。每天你可以指示机器人访问恰好 #cf_span[k] 个不同的位置。如果这些位置中没有宝藏，机器人显然会空手而归。然而，洞穴内一片漆黑，即使机器人访问了正确的地点，也可能错过宝藏。形式上，如果访问的位置中有一个包含宝藏，机器人成功获取它的概率为 #cf_span[1 / 2]，否则它将空手返回。每次机器人搜索包含宝藏的位置时，其成功概率均独立于所有先前尝试（即，在搜索正确位置 #cf_span[x] 次后仍未获得宝藏的概率为 #cf_span[1 / 2x]）。若你为机器人选择最优的调度策略，获得宝藏所需的期望天数是多少？请以模 #cf_span[109 + 7] 的有理数形式输出答案。形式上，设答案为最简分数 #cf_span[P / Q]，则你需要输出。题目保证 #cf_span[Q] 不被 #cf_span[109 + 7] 整除。第一行包含测试用例数 #cf_span[T]（#cf_span[1 ≤ T ≤ 1000]）。接下来的 #cf_span[T] 行每行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 5·108]）。对每个测试用例，在单独一行输出答案。在第一个测试用例中，机器人将反复搜索唯一的一个位置。此情况下期望天数为 2。请注意，尽管我们从一开始就已知宝藏的位置，机器人仍需持续搜索直至成功获取宝藏。在第二个测试用例中，若我们交替搜索两个位置，则答案可证明为 #cf_span[7 / 2]。在第三个测试用例中，答案为 #cf_span[25 / 9]。 ## Input 第一行包含测试用例数 #cf_span[T]（#cf_span[1 ≤ T ≤ 1000]）。接下来的 #cf_span[T] 行每行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 5·108]）。 ## Output 对每个测试用例，在单独一行输出答案。 [samples] ## Note 在第一个测试用例中，机器人将反复搜索唯一的一个位置。此情况下期望天数为 2。请注意，尽管我们从一开始就已知宝藏的位置，机器人仍需持续搜索直至成功获取宝藏。在第二个测试用例中，若我们交替搜索两个位置，则答案可证明为 #cf_span[7 / 2]。在第三个测试用例中，答案为 #cf_span[25 / 9]。

**Definitions** Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq k \leq n $. Let the treasure be uniformly at random in one of $ n $ spots. Each day, the robot visits exactly $ k $ distinct spots. If the treasure is in one of the visited spots, it is recovered with probability $ \frac{1}{2} $, independently each day. **Constraints** $ 1 \leq T \leq 1000 $, and for each test case: $ 1 \leq k \leq n \leq 5 \cdot 10^8 $. **Objective** Find the minimal expected number of days to recover the treasure under optimal scheduling, expressed as $ \frac{P}{Q} \mod (10^9 + 7) $, where $ \frac{P}{Q} $ is irreducible. The optimal strategy is to sample $ k $ distinct spots each day without repetition until all spots are covered, then repeat. Let $ p = \frac{k}{n} \cdot \frac{1}{2} $ be the probability of success per day. Then the expected number of days is $ \frac{1}{p} = \frac{2n}{k} $. Thus, the answer for each test case is: $$ \frac{2n}{k} $$

Samples

Input #1

Output #1

2
500000007
777777786

API Response (JSON)

{
  "problem": {
    "name": "G. El Toll Caves",
    "description": {
      "content": "The prehistoric caves of El Toll are located in Moià (Barcelona). You have heard that there is a treasure hidden in one of _n_ possible spots in the caves. You assume that each of the spots has probab",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF868G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The prehistoric caves of El Toll are located in Moià (Barcelona). You have heard that there is a treasure hidden in one of _n_ possible spots in the caves. You assume that each of the spots has probab...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "El Toll 的史前洞穴位于莫亚（巴塞罗那）。你听说宝藏隐藏在洞穴中的 #cf_span[n] 个可能位置之一。你假设每个位置包含宝藏的概率均为 #cf_span[1 / n]。\n\n你无法亲自进入洞穴，因此你制造了一台机器人来搜索洞穴中的宝藏。每天你可以指示机器人访问恰好 #cf_span[k] 个不同的位置。如果这些位置中没有宝藏，机器人显然会空手而归。然而，洞穴内一片漆黑，即使机器人访问了正...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n $.  \nLet the treasure be uniformly at random in one of $ n $ spots.  \nEach day, the robot visits exactly $ k $ distinct spots.  \n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments