题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=6656

题目：

若当前等级为，花掉元有的概率升级到等级，有的概率降到等级 (1≤≤i)

问从等级升级的等级需要的花费的期望值

输入：测试样例t，n个等级，q个询问，每个等级给出对应的，其中用表示，每个询问给出。注意可以从等级n升级到等级n+1

Sample Input

1 
3 2
1 1 1 2 
1 2 1 3 
1 3 3 4 
1 4 
3 4

Sample Output

22

12

 

解题思路：

dp[i]表示从等级1升级到等级i花费的期望值

无论转化成哪个等级都需要花费元，若转化为等级,那么也能转化为

因为每次只能升级一步，且 ≤ ,所以在从等级1升级到等级的过程中一定会经过等级，根据期望dp减法可知：

等价于,其中

可以推出如下递推式：

化简有：，在计算时，因为是分数，化成小数会存在误差，故把它们直接转化成逆元来计算

 

ac代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
struct node{
    ll r, s, x, a;
}d[maxn];
ll dp[maxn];
ll n, q, t;
int L, R;
ll qpow(ll a, ll b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
ll getInv(ll a, ll b) // a/b
{
    return (a * qpow(b, mod - 2)) % mod;
}
int main() {
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld %lld", &n, &q);
        for(int i = 1; i <= n; i++)
            scanf("%lld %lld %lld %lld", &d[i].r, &d[i].s, &d[i].x, &d[i].a);
        dp[1] = 0;
        for(int i = 1; i <= n; i++)
        {
            ll p1 = getInv(d[i].s - d[i].r, d[i].s);//1-（p的逆元）= （1-p）的逆元
            ll p2 = getInv(d[i].s, d[i].r);//（1/p）的逆元
            dp[i + 1] = (p2 * ((d[i].a + dp[i]) % mod - (p1 * dp[d[i].x]) % mod + mod) % mod) % mod;
        }
        int L,R;
        for(int i = 1; i <= q; i++)
        {
            scanf("%d%d",&L, &R);
            printf("%lld\n",(dp[R] - dp[L] + mod) % mod);
        }
    }
    return 0;
}