萌新求助分治FFT
查看原帖
萌新求助分治FFT
115857
too_later楼主2021/7/5 10:08

全 WA 了。

#include<bits/stdc++.h>
#define I inline
#define RI register int
#define rep(i,a,b) for(RI i=a;i<=b;++i)
#define dow(i,a,b) for(RI i=a;i>=b;--i)
using namespace std;
const int N=2e6+5,mo=998244353;
I int add(int a,int b){ return a+b>=mo?a+b-mo:a+b; }
I int sub(int a,int b){ return a-b<0?a-b+mo:a-b; }
I int mul(int a,int b){ return 1ll*a*b%mo; }
int n,R[N],g[N],c[N],d[N],f[N];
I int fast(int a,int b,int mo){
	RI res=1;while(b){ if(b&1) res=mul(res,a);a=mul(a,a),b>>=1; } return res; }
I void NTT(int a[],int lim,int op){
	rep(i,1,lim-1) if(R[i]>i) swap(a[R[i]],a[i]);
	for(RI i=1;i<lim;i<<=1){
		RI now=fast(op==1?3:332748118,(mo-1)/(i<<1),mo);
		for(RI j=0;j<lim;j+=(i<<1)){
			RI res=1;
			rep(k,0,i-1){
				RI x=a[j+k],y=mul(res,a[j+k+i]);
				a[j+k]=add(x,y),a[j+k+i]=sub(x,y),res=mul(res,now);
			}
		}
	}
	RI now=fast(lim,mo-2,mo);
	rep(i,0,lim-1) if(op==-1) a[i]=mul(a[i],now);
}
I void solve(int l,int r,int lg){
	if(l==r||l>n) return;
	RI mid=l+r>>1;solve(l,mid,lg-1);
	rep(i,1,1<<lg) R[i]=R[i>>1]>>1|(i&1)<<lg-1;
	rep(i,l,mid) c[i-l]=f[i];rep(i,mid+1,r) c[i-l]=0; 
	rep(i,0,r-l) d[i]=g[i];
	NTT(c,1<<lg,1),NTT(d,1<<lg,1);
	rep(i,0,1<<lg) c[i]=mul(c[i],d[i]);
	NTT(c,1<<lg,-1);
	rep(i,mid+1,r) f[i]=add(f[i],c[i-l]);
	rep(i,0,r-l) d[i]=0;
	rep(i,0,1<<lg) c[i-l]=0;
	solve(mid+1,r,lg-1);
}

int main(){
	scanf("%d",&n),f[0]=1;
	rep(i,1,n-1) scanf("%d",&g[i]);
	RI lim=1,cnt=0;while(lim<=(n<<1)) lim<<=1,++cnt;
	solve(0,n-1,cnt);
	rep(i,0,n-1) printf("%d ",f[i]);
	return 0;
}
2021/7/5 10:08
加载中...