题目概述

有 $n$ 个数 $a_i$ ，求每个数的逆元。

解题报告

$O(n)$ 求 $n$ 个数逆元？？？

Orz WA自动机，感觉这个技巧非常有用，帮助我解决了CC的某道毒瘤题（CC比赛还没结束，就先鸽了）。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=5000000,MOD=1e9+7,PW=998244353;

int n,a[maxn+5],s[maxn+5],sv[maxn+5],INV[maxn+5],ans;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);s[0]=1;for (int i=1;i<=n;i++) readi(a[i]),s[i]=(LL)s[i-1]*a[i]%MOD;
    sv[n]=Pow(s[n],MOD-2);for (int i=n-1;i;i--) sv[i]=(LL)sv[i+1]*a[i+1]%MOD;
    for (int i=1;i<=n;i++) INV[i]=(LL)sv[i]*s[i-1]%MOD;
    for (int i=n,pw=1;i;i--,pw=(LL)pw*PW%MOD) AMOD(ans,(LL)INV[i]*pw%MOD);printf("%d\n",ans);return 0;
}