蒟蒻刚学FFT 1ns,求调
查看原帖
蒟蒻刚学FFT 1ns,求调
549499
Disjoint_cat楼主2022/12/2 20:57

样例都没过,只对了前两个数

#include<bits/stdc++.h>
#define ll long long
#define YJL_DRC_LCH_WJY_WQY_ZZH using
#define AK namespace
#define IOI std
#define db double
YJL_DRC_LCH_WJY_WQY_ZZH AK IOI;
const int N=200005;
const ll MOD=998244353;
const db PI=acos(-1.0),eps=1e-8;
struct clx
{
	db re,im;
	clx(db re=0,db im=0):re(re),im(im){}
	clx operator+(const clx B)const{return clx(re+B.re,im+B.im);}
	clx operator-(const clx B)const{return clx(re-B.re,im-B.im);}
	clx operator*(const clx B)const
	{return clx(re*B.re-im*B.im,re*B.im+im*B.re);}
};
int type;
clx E(int k){return clx(cos(2*PI/k),type*sin(2*PI/k));}
int n,n_;
ll a[N],a_[N],b[N],b_[N];
void trans(clx* a,const int n)
{
	if(n==1)return;
	clx a0[n>>1],a1[n>>1];
	for(int i=0;i<n;i++)
		if(i&1)a1[i>>1]=a[i];
		else a0[i>>1]=a[i];
	trans(a0,n>>1);trans(a1,n>>1);
	clx t(1,0),pw=E(n);
	for(int i=0;i<n>>1;i++)
	{
		a[i]=a0[i]+t*a1[i];
		a[i+(n>>1)]=a0[i]-t*a1[i];
		t=t*pw;
	}
}
void FFT(ll* a,ll* b,const int n)
{
	clx s[n],t[n];
	for(int i=0;i<n>>1;i++)s[i]=clx(a[i],0),t[i]=clx(b[i],0);
	type=1;
	trans(s,n);trans(t,n);
	for(int i=0;i<n;i++)s[i]=s[i]*t[i];
	type=-1;
	trans(s,n);
	for(int i=0;i<n;i++)a[i]=(ll)(s[i].re/n+eps)%MOD;
}
ll pw(ll ds,ll zs)
{
	if(!zs)return 1;
	ll t=pw(ds,zs>>1);t=t*t%MOD;
	return zs&1?(t*ds%MOD):t;
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	n_=1;b_[0]=pw(a[0],MOD-2);
	while(n_<n)
	{
		for(int i=0;i<n_;i++)b[i]=b_[i]*2%MOD;
		FFT(b_,b_,n_<<1);
		FFT(b_,a,n_<<2);
		for(int i=0;i<n_<<1;i++)
			b[i]=(b[i]-b_[i]+MOD)%MOD;
		n_<<=1;
	}
	for(int i=0;i<n;i++)cout<<b[i]<<" ";
	return 0;
}
2022/12/2 20:57
加载中...