题目描述#

Hazel有n本书，编号1为n到 ，叠成一堆。当她每次抽出一本书的时候，上方的书会因重力而下落，这本被取出的书则会被放置在书堆顶。 每次有pi的概率抽取编号为i的书。她每次抽书所消耗的体力与这本书在这堆中是第几本成正比。具体地，抽取堆顶的书所耗费体力值为1 ，抽取第二本耗费体力值为2 ，以此类推。

现在 想知道，在很久很久以后（可以认为几乎是无穷的），她每次抽书所耗费的体力的期望值是多少。 最终的答案显然可以表示成a/b的形式，请输出a*(b^-1)模1e9+7的值。

【输入格式】#

第一行一个整数n 接下来n行，每行两个整数ai，bi，代表抽取第i本书的概率是ai/bi 保证所有书的概率和等于1

【输出格式】#

输出一行一个整数，代表期望值

【输入样例1】#

2
227494 333333
105839 333333

【输出样例1】#

432679642

【输入样例2】

10
159073 999999
1493 142857
3422 333333
4945 37037
2227 111111
196276 999999
190882 999999
142721 999999
34858 999999
101914 999999

【输出样例2】#

871435606

【数据规模与约定】#

对于30%的数据，1<=n<=10。 对于100%的数据，1<=n<=1000,0<=ai<=bi,bi!=0。

题解#

期望DP

P表示概率 E表示期望体力

$Ans = \sum_{i=1}^{n}{P_i*E_i}$ $= \sum_{i=1}^{n}{P_i*(1+\sum_{j=1且就i!=j}^{n}{P_{抽到j比i晚}})}$ $= \sum_{i=1}^{n}{P_i*(1+\sum_{j=1且j!=i}^{n}{\frac{P_j}{P_i+P_j}})}$

#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
const LL P = 1e9 + 7;
LL pow_mod(LL a, int b)
{
    LL ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % P;
        b >>= 1;
        a = a * a % P;
    }
    return ans;
}
LL q[1005];
int main()
{
    int n;
    scanf("%d", &n);
    LL a, b;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld", &a, &b);
        q[i] = a * pow_mod(b, P - 2) % P;
    }
    LL ans = 0;
    for (int i = 1; i <= n; i++)
    {
        LL sum = 0;
        for (int j = 1; j <= n; j++)
        {
            if (j == i)
                continue;
            sum = (sum + q[j] * pow_mod(q[i] + q[j], P - 2) % P) % P;
        }
        ans = (ans + (1 + sum) * q[i]) % P;
    }
    printf("%lld", ans);
}