模意义下的除法（逆元）

模逆元简介

给定一个数 a 和一个模 m，a 在模 m 意义下的逆元 a^{-1} 满足：

如果我们想计算 \frac{a}{b} 在模 m 意义下的结果，可以将其表示为：

其中 b^{-1} 是 b 的模逆元。

计算模逆元

对于模数 m 是质数的情况，我们可以使用费马小定理来计算模逆元。费马小定理指出：

因此：

对于模 998244353，可以通过快速幂算法来计算 b^{998244351} 来求得 b 的逆元。

快速幂算法实现

以下是 C++ 代码，用于计算 a 的 b 次幂在模 m 下的结果：

// 快速幂计算 a^b % m
long long mod_pow(long long a, long long b, long long m) {
    long long result = 1;
    a = a % m;
    while (b > 0) {
        if (b % 2 == 1) {
            result = (result * a) % m;
        }
        a = (a * a) % m;
        b /= 2;
    }
    return result;
}

// 计算 b 在模 m 下的逆元
long long mod_inverse(long long b, long long m) {
    return mod_pow(b, m - 2, m);
}

应用到问题中

在计算路径概率时，如果需要计算 \frac{w_v}{sum_u}，可以通过乘以 sum_u 的模逆元来实现：

// 计算概率时使用模逆元
long long sum_u_inverse = mod_inverse(sum_u, 998244353);
long long prob = (w_v * sum_u_inverse) % 998244353;

这样，我们就能在模 998244353 的意义下正确地进行除法操作，从而保证计算结果符合题意。