AcWing:4646. 爬树的甲壳虫

发布时间:2024年01月24日
描述:

有一只甲壳虫想要爬上一颗高度为?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;
}
文章来源:https://blog.csdn.net/2301_79973431/article/details/135822646
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。