【JZOJ4928】【NOIP2017提高组模拟12.18】A

Description

Data Constraint

对于30%的数据，n<=9
对于另外10%的数据，所有的A[i]均相等
对于另外20%的数据，A[2~n]均相等
对于100%的数据，n<=100000，1<=A[i]<=5000

Solution

我们来讨论一下n=1~3的情况。
n=1，显然 ans=1A1 .
n=2，显然 ans=1A1∗(A1+A2)+1A2∗(A1+A2)=A1+A2A1∗A2∗(A1+A2)=1A1∗A2 。
n=3……
那么，显然， ans=1A1∗A2∗……∗An .

Code

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const ll maxn=1e5+5,mo=998244353;
ll x,n,i,t,j,k,l; 
ll mi(ll y){
if (y==1) return x;
    ll t=mi(y/2);
 if (y%2) return t*t%mo*x%mo;return t*t%mo;
}
int main(){
 //freopen("data.in","r",stdin);
    scanf("%lld",&n);t=1;
for (i=1;i<=n;i++)
        scanf("%lld",&x),t=t*x%mo;
x=t;
    k=mi(mo-2);
printf("%lld\n",k);
}