https://vjudge.net/contest/349029#problem/J
题目描述：
花费a[i]，从i升到i+1级有p[i]的可能成功，失败就掉到x[i]级。问从l升到r级的期望。
分析：
dp[i]表示从1级升到i级的期望，如果要计算j升到i级，就算dp[i]-dp[j]。因为他只能一级一级升，所以从1到i,一定会经过j。
dp[i]转移到dp[i+1]，假设他经过t次后成功，那么前t-1次就是失败的，就要重新从x[i]升到i，重复t-1次。x[i]升到i的期望可以知道是dp[i]-d[x[i]]。
左边，dp[i]+a[i]是成功，右边是失败。
因为成功概率为1/t=p[i]=r[i]/s[i]。可以求出t=s[i]/r[i]，再带回上式。除法取模再用下逆元。
代码：
#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> #include <vector> #include <cmath> using namespace std; typedef long long ll; const int mod=1e9+7; const int maxn=5e5+6; ll dp[maxn]; ll mp(ll x,ll n) { ll res=1; while(n) { if(n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res; } int main() { int T; scanf("%d",&T); while(T--) { int n,q; scanf("%d%d",&n,&q); ll x[n+6],a[n+6],r[n+6],s[n+6]; for(int i=1;i<=n;i++) { scanf("%lld %lld %lld %lld",&r[i],&s[i],&x[i],&a[i]); } memset(dp,0,sizeof dp); for(int i=1;i<=n;i++) { ll t=s[i]*mp(r[i],mod-2)%mod; dp[i+1]=dp[i]+a[i]+(dp[i]-dp[x[i]]+mod)%mod*(t-1)%mod+(t-1)%mod*a[i]%mod; dp[i+1]%=mod; } for(int i=1;i<=q;i++) { int l,r; scanf("%d%d",&l,&r); printf("%lld\n",(dp[r]-dp[l]+mod)%mod); } } return 0; }
原文：https://www.cnblogs.com/studyshare777/p/12450188.html