马上就吃饭了写个题解
这个题就是说用了阶乘求逆元的思想
f[i] 前i项a[i]乘积的逆元
真是好题啊
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
int w=1,q=0;char ch=' ';
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
return w*q;
}
const int N = 5e7+5;
int n, mod = 1e9+7;
int a[N];
inline int ksm(int a, int b) {
int ans = 1, base = a;
while(b) {
if(b & 1) ans *= base, ans %= mod;
base *= base, base %= mod;
b >>=1;
}
return ans % mod;
}
int f[N], g[N];
signed main() {
cin>>n;
for(int i = 1; i <= n; i++)
a[i] = read();
int ans = 0;
g[0] = 1;
for(int i = 1; i <= n ; i++) g[i] = g[i - 1] * a[i] % mod;
f[n] = ksm(g[n], mod - 2);
for(int i = n ; i; i --) f[i - 1] = f[i] * a[i] % mod;
for(int i = 1; i <= n; i++) {
ans *= 998244353, ans %= mod;
ans += (f[i] * g[i - 1]), ans %= mod;
}
cout<<ans;
return 0;
}
我就是我不一样的验货