结果深刻体会到了多项式的毒瘤awa

推的柿子是 $\frac {F(x)+R^2(x)} {2R(x)} \equiv G(x) (mod x^n)$ 然后样例挂了。。。求助

求逆元的部分去模版测试过了，NTT应该也没问题吧。。。

#include<cstdio>
#include<cstring>
#define clr(f,len) memset(f,0,(len)<<3)
#define cpy(f,g,len) memcpy(f,g,(len)<<3)
typedef long long ll;
const ll M=5e5+5,mod=998244353ll;
ll n,G=3,invG=332748118ll,fl,t[M],f[M],_s1[M],_s2[M],_s3[M],_s4[M],_s5[M];
void swap(ll&a,ll&b){
	a^=b^=a^=b;
}
ll pow(ll a,ll b=mod-2){
	ll ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
	return ans;
}
void trpe(int len){
	if(len==fl)return;fl=len;
	for(int i=0;i<len;++i)t[i]=t[i>>1]>>1|(i&1?len>>1:0);
}
void NTT(ll*f,bool flag,int n){
	trpe(n);
	int i,k,p,len;ll w,w1;
	for(i=0;i<n;++i)if(i<t[i])swap(f[i],f[t[i]]);
	for(p=2;p<=n;p<<=1){
		len=p>>1;w1=pow(flag?G:invG,(mod-1)/p);
		for(k=0;k<n;k+=p){
			w=1;
			for(i=k;i<k+len;++i){
				ll t=f[i+len]*w%mod;
				if((f[i+len]=f[i]-t)<0)f[i+len]+=mod;
				if((f[i]=f[i]+t)>mod)f[i]-=mod;
				w=w*w1%mod;
			}
		}
	}
	if(flag)return;
	ll invn=pow(n);
	for(i=0;i<n;++i)f[i]=f[i]*invn%mod;
}
void times(ll*f,ll*g,int len){
	for(int i=0;i<len;++i)f[i]=f[i]*g[i]%mod;
}
void inv(ll*f,int m){
	#define b1 _s1
	#define b3 _s2
	#define b2 _s3
	int i,n,len;
	for(n=1;n<m;n<<=1);b1[0]=pow(f[0]);
	for(len=2;len<=n;len<<=1){
		for(i=0;i<(len>>1);++i)b3[i]=(b1[i]<<1)%mod;
		for(i=0;i<(len<<1);++i)t[i]=t[i>>1]>>1|(i&1?len:0);
		cpy(b2,f,len);
		NTT(b1,1,len<<1);times(b1,b1,len<<1);
		NTT(b2,1,len<<1);times(b1,b2,len<<1);
		NTT(b1,0,len<<1);clr(b1+len,len);
		for(i=0;i<len;++i)b1[i]=(b3[i]-b1[i]+mod)%mod;
	}
	cpy(f,b1,m);clr(b1,n+n);clr(b2,n+n);clr(b3,n+n);
	#undef b1
	#undef b2
	#undef b3
}
void sqrt(ll*f,int m){
	#define b1 _s4
	#define b2 _s5
	int i,n,len;
	for(n=1;n<m;n<<=1);b1[0]=1;
	for(len=2;len<=n;len<<=1){
		for(i=0;i<(len>>1);++i)b2[i]=(b1[i]<<1)%mod;
		inv(b2,len);
		NTT(b1,1,len);times(b1,b1,len);NTT(b1,0,len);
		for(i=0;i<len;++i)b1[i]=(f[i]+b1[i])%mod;
		NTT(b1,1,len<<1);NTT(b2,1,len<<1);
		times(b1,b2,len<<1);
		NTT(b1,0,len<<1);
	}
	cpy(f,b1,m);clr(b1,n+n);clr(b2,n+n);
	#undef b1
	#undef b2
}
signed main(){
	int i;
	scanf("%lld",&n);
	for(i=0;i<n;++i)scanf("%lld",f+i);
	sqrt(f,n);
	for(i=0;i<n;++i)printf("%lld ",f[i]);
}