出题人题解 | #流星雨#

原题解链接：https://ac.nowcoder.com/discuss/153563

概率$dpdp$。

设$T_{i}T\_i$为第$ii$天下雨的真正概率，由于第i天的概率只与第$i-1i-1$天有关，所以有

$T_i=T_{i-1}\times (p_i+P)+(1-T_{i-1})\times p_{i}T\_\{i\}=T\_\{i-1\}\; \backslash times\backslash left(p\_\{i\}+P\backslash right)+\backslash left(1-T\_\{i-1\}\backslash right)\; \backslash times\; p\_\{i\}$

复杂度：加上求逆元的复杂度，$O(nlogn)O(nlogn)$

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
LL w[100005], p[100005], T[100005], n, a, b, P;
LL fast_pow(LL a,LL b) {
	LL res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
int main () { 
	scanf("%lld%lld%lld", &n, &a, &b);
	P = 1ll * a * fast_pow(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", &a, &b);
		p[i] = a * fast_pow(b, mod - 2) % mod;
	}
	T[1] = p[1];
	for (int i = 2; i <= n; ++i) {
		T[i] += T[i - 1] * ((p[i] + P) % mod) % mod;
		T[i] += (1 - T[i - 1] + mod) % mod * p[i] % mod;
		T[i] %= mod;
	}
	LL ans = 0;
	for (int i = 1; i <= n; ++i) {
		ans += 1ll * T[i] * w[i] % mod;
		ans %= mod;
	}
	cout << ans;
	return 0;
}