오프라인 으로 역 원 을 구하 다.

일단 문제 하나 볼 게 요.
이 문 제 를 보고 우 리 는 먼저 선형 구 역 의 복잡 도 를 고려 합 니 다.
페 르 마 의 작은 정리 와 유클리드 의 \ (O (n \ (log \ p) \) 를 좀 더 생각해 보 자.
그리고 우 리 는 오프라인 역 원 을 말 한 후에 이 신기 한 알고리즘 의 타당 성 을 다시 고려 해 보 자.
우선 우리 가 알 아야 할 것 은 접두사 가 쌓 인 역 원 은 역 원 의 접두사 적 이다 (즉, 역 원 은 완전 적 이다) 는 것 이다.
증: 우 리 는 임의의 두 개의 정수 \ (a \) 와 \ (b \) 를 설정 합 니 다. 그들 이 모 \ (p \) 의미 에서 반드시 만족 하 는 것 을 보 겠 습 니 다 \ (a ^ {- 1} * b ^ {- 1} \ equiv (a * b) ^ {- 1} \ (mod \ p) \)
우 리 는 역 원 의 정의 에 따라 감 \ (a * a ^ {- 1} * b * b ^ {- 1} \ \ equiv 1 \ \ (mod \ p) \ 를 얻 을 수 있 습 니 다.
그리고 우 리 는 \ (a * b \) 를 하나의 전체 로 보고 이 전체적인 역 원 은 \ (a * b) ^ {- 1} \) 입 니 다.
우 리 는 \ (a * b) * (a * b) ^ {- 1} \ \ equiv 1 \ \ (mod \ p) \ 를 알 수 있다.
∴\((a^{-1}*b^{-1})\equiv (a*b)^{-1}\ (mod\ p)\)
이 성질 에 따라 우 리 는 \ (pre {n} \) 배열 로 \ (a {n} \) 의 접두사 적 을 저장 할 수 있 습 니 다. (접두사 와!!)
∵\(\displaystyle pre_{n}=\prod_{i=1}^{n}a_{i}\)
∴\(\displaystyle pre_{n}^{-1}=\prod_{i=1}^{n}a_{i}^{-1}\)
그리고 우 리 는 발견 할 것 이다.
\(a_{i}^{-1}=pre_{i}^{-1}*pre_{i-1}\ (1<=i<=n)\)
\(pre_{i}^{-1}=pre_{i+1}^{-1}*a_{i+1}\ (1<=i
그리고 저희 가 이 감 두 개 에 맞 춰 서 문 제 를 풀 었 죠?
우 리 는 그의 시간 복잡 도 를 고려 해 보 자. 선형 매 거 진 \ (O (n) \) + 페 르 마 소정 리 (또는 유클리드 확장) 구 \ (pre {n} ^ {- 1} \) 의 \ (O (log \ p) \)
시간 복잡 도: \ (O (n + log \ p) \)
그러나 이 문 제 는 자주 끊 길 수 있 기 때문에 우 리 는 빨리 읽 어야 한다.
이 문 제 는 마지막 으로 \ \ (\ displaystyle \ \ sum {i = 1} ^ {n} {\ frac {k ^ {i}} {a {i}}} \) 를 요구 하기 때문에 \ (\ displaystyle \ \ sum {i = 1} ^ {n} {k ^ {i} * a {i} ^ {- 1} \) 로 변환 할 수 있 습 니 다.
코드

#include
#include
#include
using namespace std;
#define LL long long 
const LL p = 1e9+7;
LL n,ans,a[5000010],pre[5000010],inv[5000010];
inline LL read()
{
	int s = 0, w = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9'){s = s * 10+ch -'0'; ch = getchar();}
	return s * w; 
}
LL ksm(LL a, LL b)
{
	LL res = 1;
	for(; b; b >>= 1)
	{
		if(b & 1) res = res * a % p;
		a = a * a % p;
	}
	return res;
}
int main()
{
	n = read(); pre[0] = 1;
	for(int i = 1; i <= n; ++i)
	{
		a[i] = read();
		pre[i] = pre[i-1] * a[i] % p; 
	}
	inv[n] = ksm(pre[n],p-2);
	for(int i = n; i >= 1; --i)
	{
		inv[i-1] = inv[i] * a[i] % p;
	} 
	LL tmp = 1;
	for(int i = n; i >= 1; --i)
	{
		ans = (ans + inv[i] * pre[i-1] % p * tmp % p) % p;
		tmp = tmp * 998244353 % p; 
	}
	printf("%lld
",ans);
	return 0;
}