题干：
现在一共有n天，第i天如果有流星雨的话，会有wiwi颗流星雨。
第i天有流星雨的概率是pipi。
如果第一天有流星雨了，那么第二天有流星雨的可能性是p2+Pp2+P，否则是p2p2。相应的，如果第i−1 (i≥2)i−1 (i≥2)天有流星雨，第i天有流星雨的可能性是pi+Ppi+P，否则是pipi。
求n天后，流星雨颗数的期望。
输入描述:
第一行三个整数，n,a,b，其中n为天数，P=abP=ab
第二行n个整数wiwi。
接下来n行，每行两个整数，x,y，第i+2行表示第i天有流星雨的概率pi=xypi=xy。
1≤n≤105, 1≤a,b,x,y,wi≤109, pi+P≤1.01≤n≤105, 1≤a,b,x,y,wi≤109, pi+P≤1.0
输出描述:
一行一个整数，为答案对109+7109+7 取模的结果。
即设答案化为最简分式后的形式为abab，其中a和b互质。输出整数 x 使得bx≡a(mod 109+7)bx≡a(mod 109+7)且0≤x<109+70≤x<109+7。可以证明这样的整数x是唯一的。
示例1
输入
2 1 3
1 1
1 2
1 2 输出
166666669 说明
第一天有流星雨第二天也有流星雨的概率是12×(12+13)12×(12+13)，然后乘以流星雨的颗数2
第一天有流星雨第二天没有流星雨的概率是12×1612×16，乘以颗数1
第一天没有，第二天有的概率12×1212×12，乘以颗数1
第一天没有，第二天也没有的概率12×1212×12，乘以颗数0。
所以流星雨颗数的期望是7676
示例2
输入
3 1 5
1 1 2
1 2
1 4
2 3 输出
763333341 解题报告：
dp[i]代表第i天下雨的真正概率。可知，第i天的概率只与第i-1天有关，递推方程容易求出，最后再乘以权值w[i]。最后输出模意义下的解。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<ctime>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
ll p[MAX],w[MAX];
ll dp[MAX];//设dp[i]为第i天下雨的真正概率，由于第i天的概率只与第i-1天有关
const ll mod = 1e9+7;
ll qpow(ll a,ll k) {
ll res = 1;
while(k) {
if(k&1) res = (res*a)%mod;
k>>=1;
a = (a*a)%mod;
}
return res;
}
int main()
{
ll n,a,b,x,y;
cin>>n>>a>>b;
ll P = a*qpow(b,mod-2)%mod;
for(int i = 1; i<=n; i++) scanf("%lld",w+i);
for(int i = 1; i<=n; i++) {
scanf("%lld%lld",&x,&y);
p[i] = x*qpow(y,mod-2)%mod;
}
for(int i = 1; i<=n; i++) {
dp[i] = dp[i-1] * (p[i]+P) %mod;
dp[i] += (1-dp[i-1]+mod)*p[i]%mod;
dp[i] %= mod;
}
ll ans = 0;
for(int i = 1; i<=n; i++) {
ans = (ans + dp[i]*w[i]%mod)%mod;
}
printf("%lld\n",ans);
return 0 ;
}
京公网安备 11010502036488号