A6146. 「USACO 2024.2 Platinum」Lazy Cow
编程题
省选/NOI-
知识点
题目描述
**题目来自 [USACO 2024 February Contest, Platinum](http://usaco.org/index.php?page=feb24results) Problem 1. [Lazy Cow](http://usaco.org/index.php?page=viewproblem2&cpid=1404)**
Bessie 正在努力为美国计算机奥林匹克二月的竞赛准备测试用例。每一分钟，她可以选择不准备测试用例，不花费能量；或者对于某个正整数 $a$，花费 $3^{a-1}$ 能量准备 $a$ 个测试用例。
Farmer John 有 $D$（$1\le D\le 2\cdot 10^5$）个需求。对于第 $i$ 个需求，他告诉 Bessie，在前 $m_i$ 分钟内她总共需要准备至少 $b_i$ 个测试用例（$1\le m_i\le 10^6,1\le b_i\le 10^{12}$）。
令 $e_i$ 为满足前 $i$ 个需求 Bessie 最小需要花费的能量。输出 $e_1,\ldots ,e_D$ 模 $10^9+7$ 的余数。
Bessie 正在努力为美国计算机奥林匹克二月的竞赛准备测试用例。每一分钟，她可以选择不准备测试用例，不花费能量；或者对于某个正整数 $a$，花费 $3^{a-1}$ 能量准备 $a$ 个测试用例。
Farmer John 有 $D$（$1\le D\le 2\cdot 10^5$）个需求。对于第 $i$ 个需求，他告诉 Bessie，在前 $m_i$ 分钟内她总共需要准备至少 $b_i$ 个测试用例（$1\le m_i\le 10^6,1\le b_i\le 10^{12}$）。
令 $e_i$ 为满足前 $i$ 个需求 Bessie 最小需要花费的能量。输出 $e_1,\ldots ,e_D$ 模 $10^9+7$ 的余数。
输入格式
输入的第一行包含 $D$。以下 $D$ 行，第 $i$ 行包含两个空格分隔的整数 $m_i$ 和 $b_i$。
输出格式
输出 $D$ 行，第 $i$ 行包含 $e_i \bmod 10^9+7$。
输入输出样例
输入 #1
4 5 11 6 10 10 15 10 30
输出 #1
21 21 25 90
输入 #2
2 100 5 100 1000000000000
输出 #2
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
输出 #3
108753959 108753959 108753959 148189797 148189797 148189797 148189797 32884410 32884410 32884410 32884410 32884410 32884410 32884410 3883759 3883759 3883759 3883759 3883759 3883759
说明/提示
- 测试点 4-5：$D\le 100$，且对于所有 $i$，$m_i\le 100$。
- 测试点 6-8：$D\le 3000$。
- 测试点 9-20：没有额外限制。
供题：Brandon Wang，Claire Zhang
- 测试点 6-8：$D\le 3000$。
- 测试点 9-20：没有额外限制。
供题：Brandon Wang，Claire Zhang