RiseOJ – 게으른 소

설명

베시는 USA Cowmputing Olympiad 2월 대회의 테스트 케이스를 준비하느라 열심이다. 매 분마다 베시는 아무 테스트도 준비하지 않고 에너지를 쓰지 않거나, 어떤 양의 정수 $$a$$ 에 대해 $3^{a-1}$ 의 에너지를 써서 테스트 케이스 $$a$$ 개를 준비할 수 있다.

농부 존에게는 $$D$$ ( $1\le D\le 2\cdot 10^5$ )개의 요구가 있다. $$i$$ 번째 요구에서 존은 베시에게 처음 $$m_i$$ 분 안에 총 $$b_i$$ 개 이상의 테스트 케이스를 준비해 두어야 한다고 말한다 ( $1\le m_i\le 10^6, 1 \leq b_i \leq 10^{12}$ ).

처음 $$i$$ 개의 요구를 만족하기 위해 베시가 써야 하는 최소 에너지를 $$e_i$$ 라 하자. $e_1,\dots,e_D$ 를 $$10^9+7$$ 로 나눈 나머지로 출력하여라.

출제: Brandon Wang, Claire Zhang

제약

배점

입력 4-5: $D\le 100$ 이고 모든 $$i$$ 에 대해 $m_i \le 100$
입력 6-8: $D\le 3000$
입력 9-20: 추가 제약 없음.

출제: Brandon Wang, Claire Zhang

입력 형식

첫째 줄에 $$D$$ 가 주어진다. 다음 $$D$$ 개의 줄 중 $$i$$ 번째 줄에 공백으로 구분된 두 정수 $$m_i$$ 와 $$b_i$$ 가 주어진다.

출력 형식

$$D$$ 개의 줄을 출력한다. $$i$$ 번째 줄에는 $e_i \text{ mod } 10^9+7$ 을 출력한다.

예제 1

입력

출력

설명

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 $3^{2}\cdot 10 = 90$ 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

출력

5
627323485

예제 3

입력

20
303590 482848034083
180190 112716918480
312298 258438719980
671877 605558355401
662137 440411075067
257593 261569032231
766172 268433874550
8114 905639446594
209577 11155741818
227183 874665904430
896141 55422874585
728247 456681845046
193800 632739601224
443005 623200306681
330325 955479269245
377303 177279745225
880246 22559233849
58084 155169139314
813702 758370488574
929760 785245728062

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2023-2024 > February > Platinum

올림피아드 > USACO > 2023-2024 > February > Platinum

태그

JudgeUSACO

게으른 소

평가 및 의견

풀이 제출