模意义下的除法（逆元）

模逆元简介

给定一个数 $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$ 的意义下正确地进行除法操作，从而保证计算结果符合题意。