难道在线IDE错了吗?
查看原帖
难道在线IDE错了吗?
114914
一只书虫仔楼主2020/6/30 14:39

rt,做这道题时,把数据下载下来会对,但是提交上去就不会,并且在线IDE和评测机的结果还不同,望解答。

代码:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<iostream>
#include<algorithm> 
#include<queue>
#include<cmath>
#include<cstdio>
#define ll long long
#define inf 2147098934832ll
using namespace std;
int read(){int ans=0,f=1;char a=getchar();while(a>'9'||a<'0'){if(a=='-')f=-1;a=getchar();}while(a>='0'&&a<='9')ans=(ans<<3)+(ans<<1)+a-'0',a=getchar();return ans*f;}
const int maxn = 3000005;
const double pi = 3.141592653589793238462643383279;
int n,m,limit=1;
struct cp{
	double x,y;
	cp(double xx=0,double yy=0){x=xx,y=yy;}
}f[maxn],g[maxn];
cp operator + (cp a,cp b){return cp(a.x+b.x,a.y+b.y);}
cp operator - (cp a,cp b){return cp(a.x-b.x,a.y-b.y);}
cp operator * (cp a,cp b){return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
void fast_fast_tle(int len,cp *a,double type){ 
	if(len==1)return;
	cp a1[len>>1],a2[len>>1];
	for(int i=0;i<=len;i+=2)a1[i>>1]=a[i],a2[i>>1]=a[i+1];
	fast_fast_tle(len>>1,a1,type);
	fast_fast_tle(len>>1,a2,type);
	cp wn=cp{cos(2*pi/len),type*sin(2*pi/len)},w=cp(1,0);//w^2k_n=cos()
	for(int i=0;i<len/2;i++,w=w*wn){
		cp hd=w*a2[i];
		a[i]=a1[i]+hd;
		a[i+len/2]=a1[i]-hd;
	}
}
int main(){
    n=read();m=read();
    for(int i=0;i<=n;i++)f[i].x=read();
    for(int i=0;i<=m;i++)g[i].x=read();
    while(limit<=n+m)limit*=2;
	fast_fast_tle(limit,f,1);
	fast_fast_tle(limit,g,1);
	for(int i=0;i<=limit;i++)f[i]=f[i]*g[i];
    fast_fast_tle(limit,f,-1);
    for(int i=0;i<=n+m;i++)printf("%d ",(int)(f[i].x/limit+0.5));
	return 0;
}
2020/6/30 14:39
加载中...