Submission #421362

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX

#include <complex>



typedef complex<double> comp;
typedef vector<comp> poly;
typedef vector<comp> vec;

comp zeta;
vec circ;
int n;

void cout(comp c){
	printf("%lf + %lf i\n",c.real(),c.imag());
}

void init(int p){
	n=1;
	while(n<p)n*=2;
	
	double pi = 3.1415926535;
	zeta = comp(cos(pi*2.0/n),sin(pi*2.0/n));
	//cout(zeta);
	circ.push_back(comp(1,0));
	rep(i,n){
		circ.push_back(circ[i]*zeta);
	}
}

void invinit(){
	
	double pi = 3.1415926535;
	zeta = comp(cos(pi*2.0/n),-sin(pi*2.0/n));
	//cout(zeta);
	circ.clear();
	circ.push_back(comp(1,0));
	rep(i,n){
		circ.push_back(circ[i]*zeta);
	}
}

void vout(vec v){
	printf("vout %d\n",v.size());
	rep(i,v.size()){
		cout(v[i]);
	}
}



vec dft(poly po,int b){ //poから高速フーリエ変換したのを返す
	//po(0)からpo(n-1)までのb個を、n/b間隔で求める
	//printf("fft\n");
	//printf("%d %d\n",po.size(),b);
	vec res;
	if(b==1){
		res.push_back(po[0]);
	}
	else{
		poly p1,p2;
		rep(i,po.size()/2){
			p1.push_back(po[i*2]);
			p2.push_back(po[i*2+1]);
		}
		vec v1 = dft(p1,b/2),
			v2 = dft(p2,b/2);
		
		comp z = 1;
		//cout(z);
		rep(i,b){
			res.push_back(v1[i%(b/2)]+z*v2[i%(b/2)]);
			z*=circ[n/b];
		}
	}
	
	/*
	printf("%d\n",b);
	rep(i,b){
		cout(res[i]);
	}*/
	
	return res;
}



vec solve(poly p1,poly p2){
	vec p1v = dft(p1,n);
	//vout(p1v);
	vec p2v = dft(p2,n);
	//vout(p2v);
	
	invinit();
	
	poly fp;
	rep(i,n){
		fp.push_back(p1v[i]*p2v[i]);
	}
	
	vec res = dft(fp,n);
	return res;
}

int main(void){
	/*
	init(4);
	poly p;
	vec v = dft(p,n);
	
	
	rep(i,n){
		printf("%lf + %lf i\n",v[i].real(),v[i].imag());
	}*/
	
	int in;
	poly p1,p2;
	
	scanf("%d",&in);
	rep(i,in){
		double a,b;
		scanf("%lf%lf",&a,&b);
		p1.push_back(comp(a,0));
		p2.push_back(comp(b,0));
	}
	
	
	init(in*2);
	
	rep(i,n-in){
		p1.push_back(comp(0,0));
		p2.push_back(comp(0,0));
	}
	
	vec ans = solve(p1,p2);
	
	//vout(ans);
	
	printf("0\n");
	rep(i,in*2-1){
		
		printf("%lld\n",((lli)((ans[i].real()+0.00001)/n)));
	}
	
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void vout(vec)’:
./Main.cpp:65:29: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::vector<std::complex<double> >::size_type {aka long unsigned int}’ [-Wformat=]
  printf("vout %d\n",v.size());
                             ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:140:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&in);
                 ^
./Main.cpp:143:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lf%lf",&a,&b);
                        ^

Judge Result