牛客练习赛39 C 流星雨 (概率dp)

题意：

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

第1天有流星雨的概率是p1。

如果第i−1 (i≥2)天有流星雨，第i天有流星雨的可能性是pi+P，否则是pi。

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

分数以逆元形式输出

 

思路：

直接在逆元情况下做

第i天有流星雨的概率为t[i]=t[i-1]*(p[i-1]+P)+(1-t[i-1])*p[i]

注意减法的时候要加mod

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#include<functional>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

#define lowbit(x) ((x)&(-x))

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-;

const int mod = 1e9+;

const int maxn = 2e6+;

const int maxm = 2e6+;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

ll fp(ll a,ll n){

    ll ans = ;

    while(n){

        if(n&)ans*=a;

        n>>=;

        a*=a;

        a%=mod;

        ans%=mod;

    }

    return ans;

}

ll f[maxn],t[maxn],w[maxn];

ll p;

int main() {

    ll n, a, b;

    scanf("%lld %lld %lld", &n, &a, &b);

    p = a*fp(b,mod-)%mod;

    for(int i = ; i <=n; i++){

        scanf("%lld", &w[i]);

    }

    for(int i = ; i <= n; i++){

        scanf("%lld %lld", &a, &b);

        f[i] = a*fp(b,mod-)%mod;

    }

    ll tmp = ;

    ll ans = f[]*w[]%mod;

    t[]=f[];

    for(int i = ; i <= n; i++){

        t[i] += t[i-]*(f[i]+p)%mod+(-t[i-]+mod)*f[i]%mod;

        t[i]%=mod;

        ans+=t[i]*w[i]%mod;

        ans%=mod;

    }

    printf("%lld",ans);

    return ;

}