06736. USACO·懒惰的奶牛 · 林老师的题库

题目描述

Bessie 正在努力为美国件算机奥林匹克二月的竞赛准备测试用例。每一分钟，她可以选择不准备测试用例，不花费能量；或者对于某个正整数 $a$ ，花费 $3^{a - 1}$ 能量准备 $a$ 个测试用例。

Farmer John 有 $D$ （ $1 \leq D \leq 2 \cdot 1 0^{5}$ ）个需求。对于第 $i$ 个需求，他告诉 Bessie，在前 $m_{i}$ 分钟内她总共需要准备至少 $b_{i}$ 个测试用例（ $1 \leq m_{i} \leq 1 0^{6}, 1 \leq b_{i} \leq 1 0^{12}$ ）。

令 $e_{i}$ 为满足前 $i$ 个需求 Bessie 最小需要花费的能量。输出 $e_{1}, \dots, e_{D}$ 模 $1 0^{9} + 7$ 的余数。

输入格式

输入的第一行包含 $D$ 。以下 $D$ 行，第 $i$ 行包含两个空格分隔的整数 $m_{i}$ 和 $b_{i}$ 。

输出格式

输出 $D$ 行，第 $i$ 行包含 $e_{i} mod 1 0^{9} + 7$ 。

样例

输入

输出

提示说明

【样例解释】

测试点 6-8： $D \leq 3000$ 。
测试点 9-20：没有额外限制。

【数据规模与约定】

测试点 4-5： $D \leq 100$ ，且对于所有 $i$ ， $m_{i} \leq 100$ 。
测试点 6-8： $D \leq 3000$ 。
测试点 9-20：没有额外限制。

供题：Brandon Wang，Claire Zhang

06736. USACO·懒惰的奶牛 未做

题目描述

输入格式

输出格式

样例

提示说明

06736. USACO·懒惰的奶牛未做