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

摘要： 題目 LOJ #152. 乘法逆元 2 題解 一個奇技淫巧qwq。可以離線求乘法逆元，效率\(O(n+log(mod))\) 。 考慮處理出\(s_n\) 表示\(\prod_{i=1}^na_i\) 。...

題目

LOJ #152. 乘法逆元 2

題解

一個奇技淫巧qwq。可以離線求乘法逆元，效率\(O(n+log(mod))\) 。

考慮處理出\(s_n\) 表示\(\prod_{i=1}^na_i\) 。以及\(sinv_n\) 表示\(\prod_{i=1}^na_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 5000010

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);
}