C++14(g++5.4) 解法, 执行用时: 135ms, 内存消耗: 3100K, 提交时间: 2020-02-04 11:17:11

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1<<21,mod=998244353,sq2=116195171,P=998244353,G=3, Gi=332748118;
int n,m,len,ans;
int a[maxn];
int qpow(int x, int y)
{
    int res=1;
    while (y)
    {
        if (y & 1) res = 1ll * res*x%mod;
        x = 1ll * x*x%mod;
        y >>= 1;
    }
    return res;
}
int l=18,r[maxn];
void NTT(int *A,int limit,int opt){
    for(int i=0;i<limit;i++)
        if(i<r[i]) swap(A[i],A[r[i]]);
    for(int i=1;i<limit;i<<=1){
        int wn=qpow((opt==1)?G:Gi,(P-1)/(i<<1));
        for(int p=i<<1,j=0;j<limit;j+=p){
            int w=1;
            for(int k=0;k<i;k++,w=1LL*w*wn%P){
                int x=A[j+k],y=1LL*w*A[j+i+k]%P;
                A[j+k]=(x+y)%P; A[j+i+k]=(x-y+P)%P;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&m);
        a[m]=(a[m]+qpow(sq2,P-1-(1LL*m*m%(P-1))))%P;
    }
    n=1<<18;
    for(int i=0;i<n;++i)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(a,n,1);
    for(int i=0;i<n;++i) a[i]=1LL*a[i]*a[i]%P;
    NTT(a,n,-1); int o=qpow(n,P-2);
    for(int i=0;i<n;++i) a[i]=1LL*a[i]*o%P;
    int ans=0;
    for(int i=0;i<n;++i)
        ans=(ans+1LL*a[i]*qpow(sq2,1LL*i*i%(P-1)))%P;
    printf("%d\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 121ms, 内存消耗: 2992K, 提交时间: 2020-02-01 22:29:15

#include <bits/stdc++.h>
using namespace std;
const int e = 116195171;
const int P = 998244353, G=3, Gi=332748118;
const int N = 1<<21;
int fpow(int x,int p){
    int rs=1;
    while(p){
        if(p&1) rs=1LL*rs*x%P;
        x=1LL*x*x%P; p>>=1;
    }
    return rs;
}
int l=18,r[N];
void NTT(int *A,int limit,int opt){
    for(int i=0;i<limit;i++)
        if(i<r[i]) swap(A[i],A[r[i]]);
    for(int i=1;i<limit;i<<=1){
        int wn=fpow((opt==1)?G:Gi,(P-1)/(i<<1));
        for(int p=i<<1,j=0;j<limit;j+=p){
            int w=1;
            for(int k=0;k<i;k++,w=1LL*w*wn%P){
                int x=A[j+k],y=1LL*w*A[j+i+k]%P;
                A[j+k]=(x+y)%P; A[j+i+k]=(x-y+P)%P;
            }
        }
    }
}
int a[N],b[N],n,m;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&m);
        a[m]=(a[m]+fpow(e,P-1-(1LL*m*m%(P-1))))%P;
    }
    n=1<<18;
    for(int i=0;i<n;++i)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(a,n,1);
    for(int i=0;i<n;++i) a[i]=1LL*a[i]*a[i]%P;
    NTT(a,n,-1); int o=fpow(n,P-2);
    for(int i=0;i<n;++i) a[i]=1LL*a[i]*o%P;
    int ans=0;
    for(int i=0;i<n;++i)
        ans=(ans+1LL*a[i]*fpow(e,1LL*i*i%(P-1)))%P;
    printf("%d\n",ans);
}