专栏文章

题解：P5431 【模板】模意义下的乘法逆元 2

sshinzAnmonoszm 妹妹
P5431题解参与者 4已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miojt155
此快照首次捕获于
2025/12/02 20:22
3 个月前
此快照最后确认于
2025/12/02 20:22
3 个月前
查看原文

算法介绍

O(n+log⁡p)O(n+\log p) 的计算形如 (∑i=1naibi) mod p\left(\sum_{i=1}^{n}\dfrac{a_i}{b_i}\right)\bmod p 式子的值。
设所有 bib_i 的积为 SS。
(∑i=1naibi) mod p=(∑i=1naiSbi)S mod p=∑i=1nai∏j=1i−1bj∏j=i+1nbjS mod p\begin{aligned} \left(\sum_{i=1}^{n}\dfrac{a_i}{b_i}\right)\bmod p&= \frac{\left(\sum_{i=1}^{n}\dfrac{a_iS}{b_i}\right)}{S}\bmod p\\ &=\dfrac{\sum_{i=1}^n a_i\prod_{j=1}^{i-1}b_j\prod_{j=i+1}^nb_j}{S} \bmod p \end{aligned}
O(N)O(N) 预处理出 bib_i 数组的前缀积和后缀积，使用费马小定理求一次逆元即可。

正确性证明

由上述描述，时间复杂度显然正确。当然，对于本题，需要边循环边维护 kik^i。

参考代码

CPP
#include<cstdio>
using ll = long long;
const int sz = 5e6 + 10;
ll pre[sz], suf[sz], arr[sz], mod, up, k, n;
inline ll qpow(ll base,ll exp){
    ll ans=1;
    while(exp!=0){
        if(exp&1)ans=ans*base%mod;
        base=base*base%mod,exp>>=1;
    }
    return ans;
}
inline ll read() {
    char ch = getchar();
    ll x = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') 
        x = x * 10 + ch - '0', ch = getchar();
    return x;
}
int main() {
    n = read(), mod = read(), k = read();
    pre[0] = 1;
    for (register int i = 1; i <= n; i++) 
        arr[i] = read(), pre[i] = arr[i] * pre[i - 1] % mod;
    suf[n + 1] = 1;
    for (register int i = n; i; i--) 
        suf[i] = arr[i] * suf[i + 1] % mod;
    for (register ll i = 1, p = k; i <= n; i++, p = p * k % mod) 
        up = (up + p * pre[i - 1] % mod * suf[i + 1] % mod) % mod;
    printf("%lld\n", up * qpow(suf[1],mod-2) % mod);
    return 0;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...