C++14(g++5.4) 解法, 执行用时: 121ms, 内存消耗: 11612K, 提交时间: 2018-10-04 13:44:52

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn=210000;
const LL P=998244353; //P=C*2^k+1£¬PÊÇÖÊÊý
const LL mod=998244353;
const LL g=3; //PµÄÔ­¸ù
int N,na,nb;
LL a[maxn*2],b[maxn*2],W[2][maxn*2],rev[maxn*2],f[maxn*2],tmp[maxn*2];
LL inv[410000];
LL ff[410000];
LL fac[410000];
LL pow_mod(LL a,int b)
{
	LL c=1;
	for (;b; b>>=1,a=a*a%P) if (b&1) c=c*a%P;
	return c;
}
void NTT(LL*a,int f,int N)
{
	for (int i=0;i<N;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
	for (int i=1;i<N;i<<=1)
		for (int j=0,t=N/(i<<1);j<N;j+=i<<1)
			for (int k=0,l=0,x,y;k<i;k++,l+=t) x=(LL)W[f][l]*a[j+k+i]%P,y=a[j+k],a[j+k]=(y+x)%P,a[j+k+i]=(y-x+P)%P;
	if (f) for (int i=0,x=pow_mod(N,P-2);i<N;i++) a[i]=(LL)a[i]*x%P;
}
void change(int N)
{
	for (int i=0;i<N;i++)
	{
		int x=i,y=0;
		for (int k=1; k<N; x>>=1,k<<=1) (y<<=1)|=x&1;
		rev[i]=y;
	}
}
void init(int N)
{
	W[0][0]=W[1][0]=1;
	for (int i=1,x=pow_mod(g,(P-1)/N),y=pow_mod(x,P-2); i<N; i++) 
	    W[0][i]=(LL)x*W[0][i-1]%P,W[1][i]=(LL)y*W[1][i-1]%P;
	change(N);
}
int n;
LL w[210000];
LL ans;
int main()
{
	scanf("%d",&n);
	for (int i=0;i<n;i++)
		scanf("%lld",&a[i]),b[n-1-i]=a[i];
	N=1;
	while (N<=2*n) N<<=1;
	init(N);
	NTT(a,0,N);
	NTT(b,0,N);
	for (int i=0;i<N;i++)
		a[i]=a[i]*b[i]%mod;
	NTT(a,1,N);
	fac[0]=1;
	for (int i=1;i<=n;i++)
		fac[i]=(fac[i-1]*(LL)i)%mod;
	for (int i=2;i<n;i++)
	{
		LL tmp=a[n-1-i];
		tmp=tmp*2LL;
		tmp=tmp*pow_mod(i,mod-2)%mod;
		tmp=tmp*pow_mod(i+1,mod-2)%mod;
		ans=(ans+tmp)%mod;
	}
	cout<<ans<<endl;	
	return 0;
}

C++ 解法, 执行用时: 117ms, 内存消耗: 6672K, 提交时间: 2021-10-16 17:48:33

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const LL mod=998244353;
const LL G=3;
const LL MAXN=1e7 + 100;
LL rev[MAXN];
LL lim=1;
LL ksm(LL a,LL b)
{
	LL res=1;
	while(b)
	{
		if(b&1)
		res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

void ntt(LL  *a,LL  opt)
{
	LL inv=ksm(lim,mod-2),invG=ksm(3,mod-2);
	for(LL  i=1;i<lim;i++)
		if(i<rev[i])swap(a[i],a[rev[i]]);
	for(LL  i=2;i<=lim;i<<=1)
	{
		LL  mid=i>>1,Wn=ksm(~opt?G:invG,(mod-1)/i),t;
		for(LL  j=0;j<lim;j+=i)
		{
			long long w=1;
			for(LL  k=j;k<j+mid;k++,w=w*Wn%mod)
			{
				t=w*a[k+mid]%mod;
				a[k+mid]=(a[k]-t+mod)%mod;a[k]=(a[k]+t)%mod;
			}
		}
	}
	if(opt==-1)for(LL  i=0;i<lim;i++)a[i]=a[i]*inv%mod;
}



LL a[MAXN];
LL b[MAXN]; 
int main()
{
	LL n;
	cin>>n;
	for(LL i=0;i<n;i++)		cin>>a[i];
	for(LL i=0;i<n;i++)		b[n-i-1]=a[i];
	LL l=-1;
	while(lim<=2*n)lim<<=1,l++;
	for(LL  i=1;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<l);
	ntt(a,1);ntt(b,1);
	for(LL i=0;i<lim;i++)
	{
		a[i]=a[i]*b[i]%mod;
	}
	ntt(a,-1);
	LL ans=0;
	for(LL i=2;i<n;i++)
	{
		ans=ans+2*a[n+i-1]%mod*ksm(i*(i+1)%mod,mod-2)%mod;	
		ans=ans%mod; 
	}
	cout<<ans<<endl;
}