洛谷P3807 模板 Lucas定理

1、当 p 为素数且 a 与 p 互质，即 (a, p) = 1 时，根据费马小定理可得 a^(p - 1) ≡ 1 (mod p)。此时 a^(p - 2) 即为 a 对 p 的模逆元。利用该逆元可以计算组合数 c(m, n) 在模 p 下的值。组合数的表达式如下：
c(m, n) = n! / (m! * (n - m)!), 其中满足条件 1 <= n < p ，且 1 <= m < p。
因此，c(m, n) % p 可表示为 (n! % p) × {(1 / (m! × (n - m)!)) % p}。
2、设数组 f[x] 表示 x! 对 p 取模后的结果，而 g(x) 表示 x! 的模逆元，即 (x!)^-1 mod p 的值。那么组合数 c(m, n) 在模 p 下的表达式可简化为：
c(m, n)(mod p) = f[n] × g[m] × g[n - m] mod p。
3、应用卢卡斯定理进行进一步处理

    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    typedef long long ll;
    using namespace std;
    const ll MaxN = 100010;
    ll f[MaxN];