rt,写的是$O(n\log n)$的牛顿迭代,虽然知道常数大但是本地$O(n\log n),n=2\times 10^5$跑了$20s$感觉还是很不对劲

能帮忙看一下是不是写挂了吗?

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline T read(T& t)
{T f=1;char ch=getchar();t=0;
while(ch<'0'||ch>'9'){if (ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')t=t*10+ch-'0',ch=getchar();t*=f;return t;}
template<typename T,typename... Args>
inline void read(T& t,Args&... args)
{read(t);read(args...);}
//小心使用static 
const long long p=998244353,G=3,Gi=332748118;
inline long long power(long long x,long long k=p-2)
{
	long long re=1;
	for(;k;k>>=1,x=(x*x)%p)if(k&1)re=(re*x)%p;
	return re;
}
int rev[800005];
void NTT(long long *f,int lim,int flag)
{
	for(int i=0;i<lim;i++)if(i<rev[i])swap(f[i],f[rev[i]]);
	long long wn,buf,tp;
	for(int len=1;len<lim;len<<=1)
	{
		wn=power(flag==1?G:Gi,(p-1)/(len<<1));
		for(int l=0;l<lim;l+=len<<1)
			for(int i=l,buf=1;i<l+len;i++,buf=(buf*wn)%p)
			{
				tp=(f[i+len]*buf)%p;
				f[i+len]=(f[i]-tp+p)%p;
				f[i]=(f[i]+tp)%p;
			}
	}
	if(flag==1)return;
	long long Inv=power(lim,p-2);
	for(int i=0;i<lim;i++)f[i]=f[i]*Inv%p;
}
void MUL(long long *A,long long *B,long long *g,int n,int m)
{
	static long long A_[800005],B_[800005];
	static int n_,m_;n_=n;m_=m;
	m=n+m;n=1;
	while(n<m)n<<=1; 
	for(int i=0;i<n_;i++)A_[i]=A[i];
	for(int i=0;i<m_;i++)B_[i]=B[i];
	for(int i=n_;i<n;i++)A_[i]=0;
	for(int i=m_;i<n;i++)B_[i]=0;
	for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(A_,n,1);NTT(B_,n,1);
	for(int i=0;i<n;i++)g[i]=A_[i]*B_[i]%p;
	NTT(g,n,0);
	for(int i=m;i<n;i++)g[i]=0;
}
void INV(long long *f,long long *g,int m)
{
	if(m==1)return g[0]=power(f[0],p-2),void();
	INV(f,g,(m+1)>>1);
	static long long f_[800005];
	int n=1;while(n<(m<<1))n<<=1;
	for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)?n>>1:0),f_[i]=f[i];
	for(int i=m;i<n;i++)f_[i]=0;
	NTT(f_,n,1);NTT(g,n,1);
	for(int i=0;i<n;i++)g[i]=((2-g[i]*f_[i]%p+p)*g[i])%p;
	NTT(g,n,0);
	for(int i=m;i<n;i++)g[i]=0;
}
inline void jifen(long long *f,long long *g,int n){for(int i=1;i<n;i++)g[i]=(f[i-1]*power(i,p-2))%p;g[0]=0;}
inline void weifen(long long *f,long long *g,int n){for(int i=1;i<n;i++)g[i-1]=(f[i]*i)%p;g[n-1]=0;}
void LN(long long *f,long long *g,int n)
{
	static long long f_[800005],f_inv[800005],f_ln_[800005];
	for(long long *i=f_inv;i!=f_inv+(n<<2);i++)*i=0;
	for(long long *i=f_ln_;i!=f_ln_+(n<<2);i++)*i=0;
	weifen(f,f_,n);
	INV(f,f_inv,n);
	MUL(f_inv,f_,f_ln_,n,n);
	jifen(f_ln_,g,n);
}
void EXP(long long *f,long long *g,int m)
{
	if(m==1)return g[0]=1,void();
	EXP(f,g,(m+1)>>1);
	int n=1;
	while(n<m<<1)n<<=1;
	static long long g_[800005],f_[800005];
	LN(g,g_,m);
	for(int i=0;i<m;i++)f_[i]=(-g_[i]+f[i]+p)%p;
	f_[0]++;f_[0]=f_[0]%p;
	MUL(f_,g,g,m,m);
}
/*
void checker(long long * f,long long *P,int n)
{
	static long long pd[800005],pdd[800005];
	memset(pd,0,sizeof(pd));
	memset(pdd,0,sizeof(pdd));
	EXP(f,pd,n);
	INV(pd,pdd,n);
	MUL(f,pdd,pd,n,n);
	printf("checker::f:");for(int i=0;i<n;i++)printf("%lld ",f[i]);printf("\n");
	printf("checker::P:");for(int i=0;i<n;i++)printf("%lld ",P[i]);printf("\n");
	printf("checker::frac{f}{exp f}-P:");for(int i=0;i<n;i++)printf("%lld ",pd[i]-P[i]);printf("\n");
}
*/
void Newton(long long * P,long long * G,int n)//答案存在G里
{
	if(n==1)return G[0]=P[0],void();
	static long long g[800005];
	Newton(P,g,n>>1);	
	static long long Exp[800005];
	EXP(g,Exp,n);
	MUL(Exp,P,Exp,n,n);
	for(int i=0;i<n;i++)Exp[i]=(g[i]-Exp[i]+p)%p;
	static long long Inv[800005];
	for(int i=0;i<n;i++)Inv[i]=0;
	g[0]=(g[0]+p-1)%p;
	INV(g,Inv,n);
	g[0]=(g[0]+1)%p;
	MUL(Exp,Inv,Exp,n,n);
	for(int i=0;i<n;i++)
		G[i]=(g[i]+Exp[i])%p;
}
long long inv[800005];
void Solve(long long * f,int n)//先要把n补成2的次幂 
{
	if(n==1)return f[0]=0,void();//\mod x意义下只要f\equiv 0即可
	static long long g[800005];
	Solve(g,n>>1);
	static long long P[800005];
	for(int i=0;i<n;i++)P[i]=0;
	for(int k=2;k<n;k++)
		for(int i=0;i*k<n;i++)
			P[i*k]=(P[i*k]+g[i]*inv[k])%p;
	static long long PP[800005];
	EXP(P,PP,n);
	for(int i=n-1;i>=1;i--)
		PP[i]=PP[i-1];
	PP[0]=0;
	for(int i=0;i<n;i++)f[i]=0;
	Newton(PP,f,n);	
}
long long f[800005],g[400005];
int n;
int main()
{
	int n;
	read(n);
	for(int i=1;i<=400000;i++)inv[i]=power(i);
	int N=1;
	while(N<=n)N<<=1;
	Solve(f,N);
	if(n&1)
	{
		long long ans=f[n];
		for(int i=n/2+1;i<=n-1;i++)
			ans=(ans+p-f[i]*f[n-i]%p)%p;
		printf("%lld\n",ans);
	}
	else
	{
		long long ans=(f[n]-(f[n/2]-1)*(f[n/2])/2%p+p)%p;
		for(int i=n/2+1;i<=n-1;i++)
			ans=(ans+p-f[i]*f[n-i]%p)%p;
		printf("%lld\n",ans);
	}
	return 0;
}
/*
200000
174218497
*/