本文主要是介绍签到(乘法逆元),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
夭寿了多会儿的题我现在才想起补orz
链接:https://ac.nowcoder.com/acm/contest/275/A
来源:牛客网
题目描述
你在一栋楼房下面,楼房一共有n层,第i层每秒有pi的概率会扔下一个东西并砸到你
求第一秒内你被砸到的概率
输入描述:
第一行一个整数n
之后有n行,第i+1行有两个整数ai,bi,表示
输出描述:
设答案为,你只需要找到一个最小的非负整数T,使得
输出这个T就行了
示例1
输入
复制
2
1 2
1 2
输出
复制
750000006
说明
一共只有如下状态:
-
第一层和第二层都扔了下来
-
第一层扔了下来
-
第二层扔了下来
-
第一层和第二层都没有扔下来
以上四种都是等概率发生的
除了第四种情况外,都会被砸到
因此被砸到的概率是 3/4,这个值在模1e9+7意义下就是750000006
备注:
数据范围
0 ≤ n ≤ 105
1 ≤ ai ≤ bi ≤ 105
题意很简单orz虽然我概率菜的一比但也知道是一减不被砸中的概率相乘
重点就是对ai/bi的取模orz众所周知除法取模就是乘以乘法逆元,又因为费马小定理可知a*ap-2≡1(mod p)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
int n;
ll a,b,res;
ll pow_mod(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}
int main(){while(cin>>n){res=1;while(n--){cin>>a>>b;res=res*a%mod*pow_mod(b,mod-2)%mod;}cout<<(res+mod)%mod<<endl;}return 0;
}
这篇关于签到(乘法逆元)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!