题解 | #扫雷#

扫雷

题目描述

小A最近迷上了扫雷。 小A玩的扫雷游戏规则是这样的：$nn$ 个地雷排成一排，必须从 $11$ 到 $nn$ 依次扫过。扫一个雷需要花费 $11$ 秒 的时间，如果成功排除当前雷，则可以排除下一个雷；否则的话地雷就会引爆，游戏失败，还需要从头开始重新扫雷。扫完第 $nn$ 个雷后才会胜利，游戏结束。 因为小A太弱了，他并不会推断每个位置的雷，只能凭运气去扫雷，所以对于第 $i(1\le i\le n)i\; (1\le i\le n)$ 个雷，他有 的概率能排除成功，否则雷就会爆炸，要重新开始。 现在小A想知道作为非酋，他游戏胜利的期望用时是多少，你能帮帮可怜的他吗？

输入描述

第一行一个整数 $nn$，表示雷的个数。接下来 $nn$ 行每行两个正整数 $a_{i}a\_i$，$b_{i}b\_i$，意义如上所述。

输出描述

输出一行一个数表示小A游戏胜利的期望用时，答案对 $10000000071000000007$ 取模。

样例

输入

3
1 2
1 2
1 2

输出

14

数据范围

$n\le 10^6,1\le a_i,b_i\le 10^{9}n\le 10^6,1\le a\_i,b\_i\le 10^9$。

题解

思路

考虑递推。

设 $f_{i}f\_i$ 为成功扫完 $ii$ 个雷的期望时间，$p_i=\frac{a_i}{b_i}p\_i=\backslash frac\{a\_i\}\{b\_i\}$，

则 $f_i=(f_{i-1}+1){\sum }_{k=1}^{\mathrm{\infty }}k{p}_i(1-p_i{)}^{k-1}=\frac{f_{i-1}+1}{p_i}=a_i^{-1}{b}_i(f_{i-1}+1)f\_i=(f\_\{i-1\}+1)\backslash sum\; \_\{k=1\}^\{\backslash infty\; \}kp\_i(1-p\_i)^\{k-1\}=\backslash frac\{\; f\_\{i-1\}+1\}\{p\_i\}\; =a\_i^\{-1\}b\_i(f\_\{i-1\}+1)$。

时间复杂度

$O(n\log mod)O(n\backslash log\; mod)$。

C++ 代码

#include <iostream>

using namespace std;

const int N = 1000010, mod = 1e9+7;

#define LL long long

LL qpow(LL a, LL b, LL p){
    LL res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res % p;
}

int main(){
    LL n, res = 0;
    cin >> n;
    while (n -- )
    {
        LL a, b;
        cin >> a >> b;
        res = (res + 1) * b % mod * qpow(a, mod - 2, mod) % mod;
    }
    cout << res << endl;
    return 0;
}