对质数取模结果(扩展欧几里得算法模板)爬树甲壳虫

问题描述

有一只甲壳虫想要爬上一颗高度为 �n的树，它一开始位于树根，高度为 00，

当它尝试从高度 �−1i−1 爬到高度为 �i 的位置时有 ��Pi​ 的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。

输入格式

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

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

输出格式

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

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

样例输入 1

1
1 2

样例输出 1

2

样例输入 2

3
1 2
3 5
7 11

样例输出 2

623902744

评测用例规模与约定

对于 2020 的评测用例, �≤2,1≤��<��≤20n≤2,1≤xi​<yi​≤20;

对于 5050 的评测用例, �≤500,1≤��<��≤200n≤500,1≤xi​<yi​≤200;

对于所有评测用例, 1≤�≤100000,1≤��<��≤1091≤n≤100000,1≤xi​<yi​≤109 。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int MOD = 998244353;
ll x[maxn], y[maxn];

//快速幂模板
ll ksm(ll a, ll b, ll m)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)ans = ans * a % m;
        b >>= 1;
        a = a * a % m;
    }
    return ans;
}
//求模MOD意义下的x的逆元
ll inv(ll x)
{
    return ksm(x, MOD - 2, MOD);
}
//扩展欧几里得模板
//求解cx+dy = gcd(c, d)的解，返回值为gcd(c, d)
ll extgcd(ll c, ll d, ll&x, ll&y)
{
    ll g = c;
    if(d)
    {
       g = extgcd(d, c % d, y, x);
       y -= (c / d) * x;
    }
    else x = 1, y = 0;
    return g;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    ll a = 0, b = 0;
    for(int i = n; i >= 1; i--)
    {
        ll p = x[i] * inv(y[i]) % MOD, p_1 = (y[i] - x[i]) * inv(y[i]) % MOD;
        a = (p + p_1 * a) % MOD;
        b = (1 + p_1 * b) % MOD;
    }
    //求解cx + dy = e
    ll c = a - 1, d = MOD, e = MOD - b, x, y;
    //先求解cx + dy = gcd(c, d)
    ll g = extgcd(c, d, x, y);
    //再求解cx + dy = e
    ll ans_x = x * e / g;
    cout<<(ans_x % MOD + MOD ) % MOD<<endl;
    return 0;
}