Submission #7423586

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T>
class polynomial {
	using value_type = T;
	using size_type = size_t;

	std::vector<value_type> data;
	
	public:
	polynomial() : data(1, 0) {}
	polynomial(const size_type & N) : data(N, 0) {}
	const value_type eval(const value_type & x) {
		value_type ret = data[0], tmp = x;
		for(int i = 1; i < data.size(); i++) {
			ret += data[i] * tmp;
			tmp *= x;
		}
		return ret;
	}

	void resize(const size_type & N) { data.resize(N); }
	value_type & operator[](const size_type & k) { return data[k]; }
	const size_type degree() { return data.size() - 1; }
	const size_type size() { return data.size(); }
};

namespace fast_fourier_transform {
	using Real = double;
	using Complex = std::complex<Real>;
	using poly = polynomial<Complex>;
	
	const Real PI = M_PI;

	const poly DFT(poly f) {
		const int N = f.size();
		if(N == 1) return f;
		
		poly f0(N / 2);
		poly f1(N / 2);
		for(int i = 0; i < f0.size(); i++) f0[i] = f[i << 1];
		for(int i = 0; i < f1.size(); i++) f1[i] = f[i << 1 ^ 1];

		poly inv_f0 = DFT(f0);
		poly inv_f1 = DFT(f1);

		poly inv_f(N);
		for(int i = 0; i < f.size(); i++) {
			Complex zeta_n_i = Complex(cos(2. * PI * i / N), sin(2. * PI * i / N));

			inv_f[i] = inv_f0[i % f0.size()] + zeta_n_i * inv_f1[i % f1.size()];
		}
		return inv_f;
	}

	const poly IDFT(poly inv_f) {
		const int N = inv_f.size();

		poly arranged = DFT(inv_f);

		poly f(N);
		for(int i = 0; i < N; i++) f[i] = arranged[(N - i) % N] / Complex(N, 0);
		return f;
	}

	const poly convolution(poly a, poly b) {
		const int sz = a.size() + b.size() - 1;

		int N = 1;
		while(N < sz) N <<= 1;
		a.resize(N);
		b.resize(N);
		
		poly inv_a = DFT(a);
		poly inv_b = DFT(b);
		poly inv_c(N);
		for(int i = 0; i < N; i++) inv_c[i] = inv_a[i] * inv_b[i];
		return IDFT(inv_c);
	}
};

int main() {
	namespace FFT = fast_fourier_transform;
	using poly = FFT::poly;
	
	int n; scanf("%d", &n); poly a(n + 1), b(n + 1);
	for(int i = 1; i < n + 1; i++) std::cin >> a[i] >> b[i];
	poly c = FFT::convolution(a, b);

	for(int i = 1; i < 2 * n + 1; i++) printf("%d\n", (int)std::round(c[i].real()));
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:99:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n); poly a(n + 1), b(n + 1);
                        ^

Judge Result