流星雨

NC22526. 流星雨

描述

现在一共有n天，第i天如果有流星雨的话，会有 $w_i$ 颗流星雨。

第i天有流星雨的概率是 $p_i$ 。

如果第一天有流星雨了，那么第二天有流星雨的可能性是

，否则是 $p_2$ 。相应的，如果第 $i-1\ (i \geq 2)$ 天有流星雨，第i天有流星雨的可能性是

，否则是 $p_i$ 。

求n天后，流星雨颗数的期望。

输入描述

第一行三个整数，n,a,b，其中n为天数，
第二行n个整数。
接下来n行，每行两个整数，x,y，第i+2行表示第i天有流星雨的概率。

输出描述

一行一个整数，为答案对取模的结果。

即设答案化为最简分式后的形式为 $\frac{a}{b}$ ，其中a和b互质。输出整数 x 使得 $bx≡a(mod \ 10^9+7)$ 且 $0 \leq x<10^9+7$ 。可以证明这样的整数x是唯一的。

示例1

输入:

输出:

166666669

说明:

第一天有流星雨第二天也有流星雨的概率是 $\frac{1}{2} \times (\frac{1}{2} + \frac{1}{3})$ ，然后乘以流星雨的颗数2

第一天有流星雨第二天没有流星雨的概率是 $\frac{1}{2} \times \frac{1}{6}$ ，乘以颗数1

第一天没有，第二天有的概率 $\frac{1}{2} \times \frac{1}{2}$ ，乘以颗数1

第一天没有，第二天也没有的概率 $\frac{1}{2} \times \frac{1}{2}$ ，乘以颗数0。

所以流星雨颗数的期望是 $\frac{7}{6}$

示例2

输入:

输出:

763333341

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

C++14(g++5.4) 解法, 执行用时: 53ms, 内存消耗: 2784K, 提交时间: 2019-02-09 21:57:19

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int _=1e5+25,yl=1e9+7;
ll f[_],P,p[_],w[_],ans,n,x,y;
ll POW(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1)res=res*x%yl;
        x=x*x%yl;y>>=1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>x>>y; P=x*POW(y,yl-2)%yl;
    for(int i=1;i<=n;++i)cin>>w[i];
    for(int i=1;i<=n;++i)cin>>x>>y,p[i]=x*POW(y,yl-2)%yl;
    for(int i=1;i<=n;++i){
        f[i]=(p[i]+P*f[i-1])%yl;
        ans+=f[i]*w[i]%yl;
    }
    cout<<ans%yl<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 74ms, 内存消耗: 2924K, 提交时间: 2019-02-08 19:36:09

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int _=1e5+25,yl=1e9+7;
ll f[_],P,p[_],w[_],ans,n,x,y;
ll POW(ll x,ll y){
	ll res=1;
	while(y){
		if(y&1)res=res*x%yl;
		x=x*x%yl;y>>=1;
	}
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>x>>y; P=x*POW(y,yl-2)%yl;
	for(int i=1;i<=n;++i)cin>>w[i];
	for(int i=1;i<=n;++i)cin>>x>>y,p[i]=x*POW(y,yl-2)%yl;
	for(int i=1;i<=n;++i){
		f[i]=(p[i]+P*f[i-1])%yl;
		ans+=f[i]*w[i]%yl;
	}
	cout<<ans%yl<<endl;
}