链接

[]

题意

从第i到i+1 的概率是p,否则就1-p跳到x你的代价是 a

然后问从l到r的最小代价是多少？

分析

sum[i] 从第一关到第i关花费的总代价前缀和

p为到i+1的概率 q为到x的概率 p+q = 1; p = ri/si;

现在是从第i跳到第i+1关的代价是

你有可能 一次就到i+1了，也有可能两次到达，或者三次。。。。 都有可能

根据期望公式有

前几次失败最后成功 概率就是 p*q^(i-1)

代码

#include
    
     using namespace std;typedef long long ll;#define sc scanf#define pr printf#define fi first#define se second#define rep(i,x,y) for(int i = x;i <= y;i++)#define rvp(i,x,y) for(int i = y;i >= x;i--)#define pb push_backconst ll mod = 1e9 + 7;const int N = 5e5 + 10;ll sum[N];ll fpow(ll x, ll y){    ll ans = 1;    while(y)    {        if(y&1) ans = ans * x % mod;        x = x * x % mod;        y >>= 1;    }    return ans;}int main(){    int t,n,q;    sc("%d",&t);    while(t--)    {        sc("%d%d",&n,&q);        rep(i,1,n)        {            int s,r; ll a,x;            sc("%d%d%lld%lld",&r,&s,&x,&a);            ll p = s * fpow(1ll*r,mod-2)%mod;           sum[i+1] = (sum[i] + p * a % mod + (s - r)* fpow(1ll*r,mod-2) % mod * ((sum[i] - sum[x] + mod)% mod) % mod )% mod;        }         //rep(i,1,n+1) cout<
     
      <<" \n"[i==n+1];        while(q--)        {            int L,R;            sc("%d%d",&L,&R);            pr("%lld\n",(sum[R] - sum[L] + mod) % mod);        }    }    return 0;}