~~orz您也在摸鱼那我就放心了~~
by StarLbright40 @ 2021-07-11 11:34:11
@[SpadeA261](/user/124218) ~~orz您也在摸鱼那我就放心了~~
by 401rk8 @ 2021-07-11 11:55:14
本人现在已经通过，就是常数有亿点大，开了O2后最大的几个点跑900ms左右。想让各位julao再看看哪里可以继续卡常。
另外提醒后人：N大约在$2^{18}$左右即可，太小会RE,太大会TLE。
[提交记录](https://www.luogu.com.cn/record/52837651)
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=1<<18;
int m,mod=998244353,p=31596;
int inv2=(mod+1)/2;
long long len=1,L;
int rev[N];
int power(int b,int p)
{
int ans=1;
while(p)
{
if(p&1) ans=1ll*ans*b%mod;
p>>=1;
b=1ll*b*b%mod;
}
return ans;
}
void add(int &x,int y)
{
x+=y;
x-=x>=mod?mod:0;
}
void sub(int &x,int y)
{
x-=y;
x+=x<0?mod:0;
}
int add(int x)
{
return x>=mod?x-mod:x;
}
int sub(int x)
{
return x<0?x+mod:x;
}
void NTT(int *x,int len,int opt)
{
for(int i=0;i<len;i++)
{
if(rev[i]>i) swap(x[i],x[rev[i]]);
}
for(int h=2;h<=len;h<<=1)
{
int gn=power(3,(mod-1)/h);
for(int i=0;i<len;i+=h)
{
int g=1;
for(int j=0;j<h/2;j++)
{
int k=i+j;
int tmp=1ll*g*x[k+h/2]%mod;
x[k+h/2]=sub(x[k]-tmp);
x[k]=add(x[k]+tmp);
g=1ll*g*gn%mod;
}
}
}
if(opt==-1)
{
reverse(x+1,x+len);
int inv=power(len,mod-2);
for(int i=0;i<len;i++) x[i]=1ll*x[i]*inv%mod;
}
}
typedef vector<int> F;
F fix(F a,int len)
{
// for(int i=0;i<a.size();i++) cout<<a[i]<<" ";
// cout<<endl;
a.resize(len);
return a;
}
void print(F a)
{
int len=a.size();
for(int i=0;i<len;i++) printf("%d ",a[i]);
printf("\n");
}
F operator+(F a,F b)
{
int lena=a.size(),lenb=b.size();
int len=max(lena,lenb);
a.resize(len);
for(int i=0;i<len;i++) add(a[i],b[i]);
return a;
}
F operator-(F a,F b)
{
int lena=a.size(),lenb=b.size();
int len=max(lena,lenb);
a.resize(len);
for(int i=0;i<len;i++) sub(a[i],b[i]);
return a;
}
F operator*(F a,int b)
{
int lena=a.size();
for(int i=0;i<lena;i++) a[i]=1ll*a[i]*b%mod;
return a;
}
F operator*(F a,F b)
{
if(a.empty()||b.empty()) return F();
int lena=a.size(),lenb=b.size();
int lenab=lena+lenb-1;
for(len=1,L=0;len<=lena+lenb;len<<=1,L++);
for(int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
a.resize(len);
b.resize(len);
NTT(&a[0],len,1);
NTT(&b[0],len,1);
for(int i=0;i<len;i++) a[i]=1ll*a[i]*b[i]%mod;
NTT(&a[0],len,-1);
return fix(a,lenab);
}
F Inv(F a)
{
int len=a.size();
if(len==1)
{
F ans;
ans.push_back(power(a[0],mod-2));
return ans;
}
F b=Inv(fix(a,(len+1)/2));
return fix(b*2-b*b*a,len);
}
F Sqrt(F a)
{
int len=a.size();
if(len==1) return F(1,sqrt(a[0]));
F b=fix(Sqrt(fix(a,(len+1)/2)),len);
return fix((b+a*Inv(b))*inv2,len);
}
inline int read()
{
int x=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch))
{
x=x*10+ch-48;
ch=getchar();
}
return x;
}
signed main()
{
// freopen("P5395.in","r",stdin);
int n=read();
F a;
for(int i=0;i<n;i++) a.push_back(read());
print(Sqrt(a));
return 0;
}
```
by SpadeA261 @ 2021-07-11 15:02:10