迭代FFT,77ptsRE#8#9,数组开了1<<21且loj/uoj都过了
查看原帖
迭代FFT,77ptsRE#8#9,数组开了1<<21且loj/uoj都过了
326780
Albert_van楼主2023/3/13 13:50

如题,F5得到了SegmentationFault所在行,是在FFT函数里面,但是(感觉)这个位置不可能出问题,具体看代码

#include <cstdio>
#include <cmath>

namespace fIO{
	char c;void re(int &x){
		x=0;c=getchar();
		while(c<'0'||c>'9') c=getchar();
		while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	}
	char st[20];int tp;
	void wr(long long n){
		if(!n) return putchar('0'),void();
		while(n) st[++tp]=n%10+48,n/=10;
		while(tp) putchar(st[tp--]);
	}
}using fIO::re;using fIO::wr;

const double pi=acos(-1);
const int N=2e6+2329;

struct cplx{double r,i;}A[N],B[N];
cplx operator+(const cplx &x,const cplx &y){
	return (cplx){x.r+y.r,x.i+y.i};
}
cplx operator-(const cplx &x,const cplx &y){
	return (cplx){x.r-y.r,x.i-y.i};
}
cplx operator*(const cplx &x,const cplx &y){
	return (cplx){x.r*y.r-x.i*y.i,x.r*y.i+x.i*y.r};
}

int r[N],n;

#include <cassert>

void FFT(cplx* a,int typ){
	for(int i=0;i<n;++i) if(i<r[i]){
		assert(r[i]>=0&&r[i]<n);//这里从来没有 Assertion Failed,r[i] 没有越界
		cplx tmp=a[i];
		a[i]=a[r[i]];//这一行 Segmentation Fault
		a[r[i]]=tmp;
	}
	for(int w=1;w<n;w<<=1){
		cplx o1=(cplx){cos(pi/w),typ*sin(pi/w)};
		for(int i=0;i<n;i+=(w<<1)){
			cplx ok=(cplx){1,0};
			for(int j=i;j<i+w;ok=ok*o1,++j){
				cplx u=a[j],d=ok*a[j+w];
				a[j]=u+d;a[j+w]=u-d;
			}
		}
	}
}

int main()
{
	freopen("P3803_8.IN","r",stdin);
	//freopen("myass.txt","w",stdout);
	int m,x;re(n);re(m);
	for(int i=0;i<=n;++i) re(x),A[i].r=x;
	for(int i=0;i<=m;++i) re(x),B[i].r=x;
	m+=n;int l=0;for(n=1;n<=m;n<<=1) ++l;
	for(int i=0;i<n;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	FFT(A,1);FFT(B,1);
	for(int i=0;i<=n;++i) A[i]=A[i]*B[i];
	FFT(A,-1);for(int i=0;i<=m;++i) wr((long long)(0.5+A[i].r/n)),putchar(' ');
}

打开其他代码对调也无果,路过能否麻烦帮看一眼,感谢

2023/3/13 13:50
加载中...