AcWing:4646. 爬树的甲壳虫

描述:

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

输入格式

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

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

输出格式

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

其中有理数?ab 对质数?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≤109。

输入样例1：

1
1 2

输出样例1：

2

输入样例2：

3
1 2
3 5
7 11

输出样例2：

623902744

假设当高度为k时，从树根爬到k所需要的期望时间是f(k)

从f(k?1)出发，爬到高度为k有两种方式：

1.直接从k?1的位置多爬一格不掉下去；
2.从k?1个的位置多爬一个的时候先掉下去了，再从底部爬完k。

得出推导式?

f(k)=(f(k?1)+1)(1?pk)+(f(k?1)+1+f(k))pk,

化简上式

f(k)=f(k?1)+1/(1?pk)

代入 pk=xk/yk

f(k)=yk(f(k?1)+1)/yk?xk

?直接用费马小定理+快速幂求逆元

以下是AC代码:

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

/* 定义 */
using namespace std;
typedef long long LL;
const int MOD = 998244353;
int n , ans = 0;

/* 快速幂模版 */
int qsm(int a , int b)
{
    int res = 1 % MOD;
    for(; b ; b >>= 1)
    {
        if(b & 1) res = 1ll * res * a % MOD;
        a = 1ll * a * a % MOD;
    }
    return res;
}

int main()
{
    /* 读入 */
    cin >> n;
    for(int i = 0 ; i < n ; i ++)
    {
        int x , y;
        cin >> x >> y;
        /* 核心 */
        ans = (ans + 1ll) * y % MOD * qsm(y - x, MOD - 2) % MOD;
    }
    cout << ans;

    return 0;
}