【数学】第十三届蓝桥杯省赛C++ A组/研究生组《爬树的甲壳虫》（C++）

【题目描述】

有一只甲壳虫想要爬上一棵高度为 n 的树，它一开始位于树根，高度为 0，当它尝试从高度 i−1 爬到高度为 i 的位置时有 Pi 的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。

【输入格式】

输入第一行包含一个整数 n 表示树的高度。

接下来 n 行每行包含两个整数 xi,yi，用一个空格分隔，表示 Pi=xi / yi。

【输出格式】

输出一行包含一个整数表示答案，答案是一个有理数，请输出答案对质数 998244353 取模的结果。

其中有理数 a / b 对质数 P 取模的结果是整数 c 满足 0≤c<P 且 c⋅b≡a(modP)。

【数据范围】

对于 20% 的评测用例，n≤2，1≤xi<yi≤20；
对于 50% 的评测用例，n≤500，1≤xi<yi≤200；
对于所有评测用例，1≤n≤100000，1≤xi<yi≤10的9次方，为了保证不出现无解的情况，额外增加限制条件 yi−xi≠998244353（如不增加此条件，则可能出现无解情况，此为比赛原题考虑不周）。

【输入样例1】

1

2

【输出样例1】

2

【输入样例2】

3
1 2
3 5
7 11

【输出样例2】

623902744

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int P = 998244353;

int n;

LL qmi(int a, int b)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = res * a % P;
        a = (LL)a * a % P;
        b >>= 1;
    }
    return res;
}

int main()
{
    scanf("%d", &n);

    int res = 0;
    while (n -- )
    {
        int x, y;
        scanf("%d%d", &x, &y);

        res = (res + 1ll) * y % P * qmi(y - x, P - 2) % P;
    }

    printf("%d\n", res);
    return 0;
}