1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
#include<algorithm>
#include<complex>
using namespace std;
const int mod=313;
const int N=5e5+5;
typedef complex<double> C;
const double Pi=3.1415926535897932384626433832795;
C fft_wi[N],inv_wi[N];
int max_exp;
void (int n) {
int i,j,k;
C t0=exp(C(0,Pi/n)),
t1=exp(C(0,-Pi/n));
max_exp=n*2;
fft_wi[0]=inv_wi[0]=1;
for(i=1;i<n;i++) {
fft_wi[i]=fft_wi[i-1]*t0;
inv_wi[i]=inv_wi[i-1]*t1;
}
}
void FFT(C A[],int n,int ty) {
int i,j,k,m,t,l;
C *wi=ty==1?fft_wi:inv_wi;
C t0,t1;
for(j=i=0;i<n;i++) {
if(i<j) swap(A[i],A[j]);
for(l=n>>1;(j^=l)<l;l>>=1);
}
for(m=1;m<n;m<<=1) {
t=max_exp/(m<<1);
for(k=0;k<n;k+=m<<1) {
for(i=k,j=0;i<k+m;i++,j+=t) {
t0=A[i];
t1=A[i+m]*wi[j];
A[i]=t0+t1;
A[i+m]=t0-t1;
}
}
}
if(ty==1) return;
t0=1.0/n;
for(i=0;i<n;i++) A[i]*=t0;
}
C S[N],T[N];
void polynomial_inverse(int A[],int B[],int len) {
if(len==1) {B[0]=1;return;}
polynomial_inverse(A,B,len>>1);
int i,j,k,M=len<<1;
for(i=0;i<len;i++) S[i]=A[i];
fill(S+len,S+M,0);
for(i=0;i<(len>>1);i++) T[i]=B[i];
fill(T+(len>>1),T+M,0);
FFT(S,M,1);FFT(T,M,1);
for(i=0;i<M;i++)
S[i]=S[i]*T[i];
FFT(S,M,-1);
for(i=0;i<M-(len>>1);i++)
S[i].real(-((long long)floor(S[i].real()+0.5))%mod),S[i].imag(0);
S[0].real((long long)floor(2-S[i].real()+0.5)%mod);
fill(S+M-(len>>1),S+M,0);
FFT(S,M,1);
for(i=0;i<M;i++)
T[i]=T[i]*S[i];
FFT(T,M,-1);
for(i=len>>1;i<len;i++)
B[i]=((long long)floor(T[i].real()+0.5))%mod;
return;
}
int n,M=1,A[N],B[N];
int main() {
int i,j,k;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&A[i]),A[i]%=mod,A[i]=A[i]?mod-A[i]:0;
A[0]=1;while(M<=n) M<<=1;init_wi(M);
polynomial_inverse(A,B,M);
printf("%dn",(B[n]+mod)%mod);
}
|
近期评论