頁面無法載入？點擊這裡可能會修復。
Placeholder

#8151
子任務

Lazy Cow 2s 1024MB

問題

Bessie is hard at work preparing test cases for the USA Cowmputing Olympiad February contest. Each minute, she can choose to not prepare any tests, expending no energy; or expend 3^{a-1} energy preparing a test cases, for some positive integer a.

Farmer John has D (1\le D\le 2\cdot 10^5) demands. For the ith demand, he tells Bessie that within the first m_i minutes, she needs to have prepared at least b_i test cases in total (1\le m_i\le 10^6, 1 \leq b_i \leq 10^{12}).

Let e_i be the smallest amount of energy Bessie needs to spend to satisfy the first i demands. Print e_1,\dots,e_D modulo 10^9+7.


輸入

The first line contains D. The ith of the next D lines contains two space-separated integers m_i and b_i.


輸出

Output D lines, the ith containing e_i \text{ mod } 10^9+7.


子任務

編號 分數 條件
#120分

D \le 100; m_i \le 100 (1 \le i \le D)

#230分

D \le 3,000

#350分

추가 제약 조건 없음


範例 #1

4
5 11
6 10
10 15
10 30
21
21
25
90

For the first test case,

  • i=1: If Bessie creates [2, 3, 2, 2, 2] test cases on the first 5 days, respectively, she would have expended 3^1 + 3^2 + 3^1 + 3^1 + 3^1 = 21 units of energy and created 11 test cases by the end of day 5.

  • i=2: Bessie can follow the above strategy to ensure 11 test cases are created by the end of day 5, and this will automatically satisfy the second demand.

  • i=3: If Bessie creates [2, 3, 2, 2, 2, 0, 1, 1, 1, 1] test cases on the first 10 days, respectively, she would have expended 25 units of energy and satisfied all demands. It can be shown that she cannot expend less energy.

  • i=4: If Bessie creates 3 test cases on each of the first 10 days she would have expended units of energy and satisfied all demands.

For each i, it can be shown that Bessie cannot satisfy the first i demands using less energy.


範例 #2

2
100 5
100 1000000000000
108753959
108753959
108753959
148189797
148189797
148189797
148189797
32884410
32884410
32884410
32884410
32884410
32884410
32884410
3883759
3883759
3883759
3883759
3883759
3883759

來源

USACO 2024 February Platinum 1번

需要登入才能撰寫程式碼。