扫雷

NC21364. 扫雷

描述

小A最近迷上了扫雷。

小A玩的扫雷游戏规则是这样的：n 个地雷排成一排，必须从 1 到 n 依次扫过。扫一个雷需要花费 1s 的时间，如果成功排除当前雷，则可以排除下一个雷；否则的话地雷就会引爆，游戏失败，还需要从头开始重新扫雷。扫完第 n 个雷后才会胜利，游戏结束。

因为小A太弱了，他并不会推断每个位置的雷，只能凭运气去扫雷，所以对于第 i (1≤i≤n) 个雷，他有 $\frac{a_i}{b_i}$ 的概率能排除成功，否则雷就会爆炸，要重新开始。

现在小A想知道作为非酋，他游戏胜利的期望用时是多少，你能帮帮可怜的他吗？

输入描述

第一行一个整数 n ，表示雷的个数。接下来 n 行每行两个正整数 a_i， b_i，意义如上所述。

输出描述

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

示例1

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 528ms, 内存消耗: 19680K, 提交时间: 2019-04-28 12:48:01

#include<bits/stdc++.h>
#define p 1000000007
inline int inv(int a,int b=p-2,int ans=1){
    for(;b;b>>=1,a=1ll*a*a%p)
        if(b&1) ans=1ll*ans*a%p;
    return ans;
}
signed main(){
    int n,s;scanf("%d",&n);
    for(int a,b,i=1;i<=n;i++)
        scanf("%d%d",&a,&b),s=1ll*(s+1)*b%p*inv(a)%p;
    printf("%d",s);
}

C++ 解法, 执行用时: 416ms, 内存消耗: 432K, 提交时间: 2022-05-21 14:51:49

#include<bits/stdc++.h>
#define p 1000000007
inline int inv(int a,int b=p-2,int ans=1)
{
	for(;b;b>>=1,a=1ll*a*a%p)
	if(b&1)
	ans=1ll*ans*a%p;
	return ans;
}
int main()
{
	int n,s;
	scanf("%d",&n);
	for(int a,b,i=1;i<=n;i++)
	scanf("%d%d",&a,&b),s=1ll*(s+1)*b%p*inv(a)%p;
	printf("%d",s);
	return 0; 
}