Submission #420315

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define repu(i, a, b) for (int i = (a); i < (b); ++i)
#define repd(i, a, b) for (int i = (a); i > (b); --i)
#define mem(a, x) memset(a, x, sizeof(a))
#define all(a) a.begin(), a.end()
#define uni(a) a.erase(unique(all(a)), a.end())
#define count_bits(x) __builtin_popcount(x)
#define count_bitsll(x) __builtin_popcountll(x)
#define least_bits(x) __builtin_ffs(x)
#define least_bitsll(x) __builtin_ffsll(x)
#define most_bits(x) 32 - __builtin_clz(x)
#define most_bitsll(x) 64 - __builtin_clz(x)

vector<string> split(const string &s, char c) {
	vector<string> v;
	stringstream ss(s);
	string x;
	while (getline(ss, x, c)) v.push_back(x);
	return v;
}

#define error(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }

void err(vector<string>::iterator it) {}

template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
	cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
	err(++it, args...);
}

typedef long long ll;
const int MOD = 1000000007;

template<class T> inline T tmin(T a, T b) {return (a < b) ? a : b;}
template<class T> inline T tmax(T a, T b) {return (a > b) ? a : b;}
template<class T> inline void amax(T &a, T b) {if (b > a) a = b;}
template<class T> inline void amin(T &a, T b) {if (b < a) a = b;}
template<class T> inline T tabs(T a) {return (a > 0) ? a : -a;}
template<class T> T gcd(T a, T b) {while (b != 0) {T c = a; a = b; b = c % b;} return a;}


typedef complex<double> C;
int fft_n;
vector<C> omega;

ll mod_pow(ll x, ll y = MOD - 2) {
    ll res = 1;
    while (y > 0) {
        if (y & 1) res = (res * x) % MOD;
        x = (x * x) % MOD;
        y >>= 1;
    }
    return res;
}

void init_fft(int n) {
	fft_n = n;
	omega.resize(n);
	double angle = 2 * M_PI / n;
	repu(i, 0, n) {
		omega[i] = C(cos(i * angle), sin(i * angle));
	}
}

void fft(vector<C> & a) {
	int n = a.size();
	if (n == 1) return;
	int half = n >> 1;
	vector<C> even(half), odd(half);
	for (int i = 0, j = 0; i < n; i += 2, ++j) {
		even[j] = a[i];
		odd[j] = a[i+1];
	}
	fft(even); fft(odd);
	for (int i = 0, fact = fft_n / n; i < half; ++i) {
		C twiddle = odd[i] * omega[i * fact];
		a[i] = even[i] + twiddle;
		a[i + half] = even[i] - twiddle;
	}
}


void mul_fft(const vector<ll> &a, const vector<ll> &b, vector<ll> &res) {
	vector<C> fa(a.begin(), a.end()), fb(b.begin(), b.end());
	int n = 1;
	while (n < 2 * max (a.size(), b.size())) n <<= 1;
	fa.resize(n); fb.resize(n);
	
	init_fft(n);
	fft(fa); fft(fb);
	repu(i, 0, n) fa[i] = conj(fa[i] * fb[i]);
	fft(fa);
	res.resize (n);
	repu(i, 0, n) {
		res[i] = (ll) (fa[i].real() / n + 0.5);
	}
}


int main(int argc, char *argv[]) {
	ios_base::sync_with_stdio(false);
	
	int n;
	
	cin >> n;
	vector<ll> A(n), B(n);
	repu(i, 0, n) cin >> A[i] >> B[i];
	
	vector<ll> ret;
	mul_fft(A, B, ret);
	printf("0\n");
	repu(i, 0, n + n - 1) printf("%lld\n", ret[i]);
	
	
	return 0;
}

Submission Info

Compile Error

./Main.cpp:28:30: warning: variadic templates only available with -std=c++11 or -std=gnu++11
 template<typename T, typename... Args>
                              ^
./Main.cpp:29:52: warning: variadic templates only available with -std=c++11 or -std=gnu++11
 void err(vector<string>::iterator it, T a, Args... args) {
                                                    ^

Judge Result