$O(n+log(mod))$求乘法逆元

henry-1202 2019-03-27 原文

题目

题解

一个奇技淫巧qwq。可以离线求乘法逆元，效率$O(n+log(mod))$。
考虑处理出$s_i$表示$a_1~a_i$的前缀积。以及$sinv_i$表示$a_1~a_i$的逆元的积。
那么对于每次询问，$sinv_i*s_{i-1}$就是答案。
$s_i$显然可以在输入的时候顺便处理出来，$sinv_n=(s_n)^{mod-2}$（如果$mod$不是质数就exgcd一下）。
对于$sinv_i(i\not = n)$，显然有$sinv_i=sinv_{i+1}*a_{i+1}$。则可以$O(n+log(mod))$求出来$sinv_i$。
总复杂度是$O(n+log(mod))$的

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define il inline

namespace io {

#define in(a) a = read()
#define out(a) write(a)
#define outn(a) out(a), putchar('\n')

#define I_int ll
inline I_int read() {
    I_int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
char F[200];
inline void write(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
}
#undef I_int

}
using namespace io;

using namespace std;

#define N 300010

const ll mod = 1e9 + 7;
int n = read();
ll sinv[N], a[N], s[N];

ll power(ll a, ll b) { ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod; b >>= 1;
    } return ans;
}

int main() { s[0] = 1;
    for(int i = 1; i <= n; ++i) {
        a[i] = read(); 
        s[i] = s[i - 1] * a[i] % mod;
    } ll ans = 0;
    sinv[n] = power(s[n], mod - 2); sinv[0] = 1; 
    for(int i = n; i; --i) sinv[i - 1] = sinv[i] * a[i] % mod;
    for(int i = 1; i <= n; ++i) {
        ll inv = sinv[i] * s[i - 1] % mod;
        ans = (ans * 998244353 + inv) % mod;
    }
    outn(ans);
}