Submission #1135020

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) //cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;

#include <complex>
#define EPS 0.5

// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size(); s << "\n";
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  s << "\n"; return s;
}


int power_of_2(int m) {
  int cnt = 0;
  while (m > 0) {
    cnt += 1;
    m >>= 1;
  }
  return 1 << cnt;
}

template<typename T>
void extend_vector(vector<T> *x, int m) {
  int m_ = (int)(*x).size();
  assert (m_ <= m);
  vector<T> tmp = *x;
  (*x).assign(m, T());
  for (int i = 0; i < m_; ++i) {
    (*x)[i] = tmp[i];
  }
}

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd dft(vcd f, int n) {
  if (n == 1) {
    return f;
  }
  vcd f0(n/2), f1(n/2);
  rep (i, n/2) {
    f0[i] = f[2 * i + 0];
    f1[i] = f[2 * i + 1];
  }
  vcd f0_ = dft(f0, n/2);
  vcd f1_ = dft(f1, n/2);
  cd zeta(cos(2 * M_PI / n), sin(2 * M_PI / n));
  cd pow_zeta(1, 0);
  rep (i, n) {
    f[i] = (f0_[i % (n/2)] + pow_zeta * f1_[i % (n/2)]);
    pow_zeta *= zeta;
  }
  return f;
}

vcd inverse_dft(vcd f, int n) {
  if (n == 1) {
    return f;
  }
  vcd f0(n/2), f1(n/2);
  rep (i, n/2) {
    f0[i] = f[2 * i + 0];
    f1[i] = f[2 * i + 1];
  }
  vcd f0_ = dft(f0, n/2);
  vcd f1_ = dft(f1, n/2);
  cd zeta(cos(2 * M_PI / n), -sin(2 * M_PI / n));
  cd pow_zeta(1, 0);
  rep (i, n) {
    f[i] = (f0_[i % (n/2)] + pow_zeta * f1_[i % (n/2)]);
    pow_zeta *= zeta;
  }
  return f;
}

vll solve(vll g, vll h) {
  int ng, nh;
  ng = (int)g.size();
  nh = (int)h.size();
  int n = power_of_2(ng + nh + 1);
  extend_vector(&g, n);
  extend_vector(&h, n);
  vcd g_(n), h_(n);
  rep (i, n) {
    g_[i] = cd(g[i], 0);
  }
  rep (i, n) {
    h_[i] = cd(h[i], 0);
  }
  vcd gg = dft(g_, n);
  vcd hh = dft(h_, n);
  debug(gg);
  debug(hh);

  vcd ff(n);
  rep (i, n) {
    ff[i] = gg[i] * hh[i];
  }
  debug(ff);
  // vcd f = inverse_dft(ff, n);
  vcd f = dft(ff, n);
  reverse(all(f));
  rep (i, n) {
    f[i] /= n;
  }
  debug(f);
  vll ret(ng + nh);
  rep (i, ng + nh) {
    ret[i] = EPS + f[i].real();
  }

  return ret;
}

int n;
int n_;
vll a, b;

int main() {
  scanf("%d", &n_);
  n_ += 1;
  a.resize(n_);
  b.resize(n_);
  a[0] = b[0] = 0;
  FOR (i, 1, n_) {
    scanf("%lld %lld", &a[i], &b[i]);
  }

  vll f = solve(a, b);
  n_ -= 1;
  rep (i, 2 * n_) {
    printf("%lld\n", f[i]);
  }

  return 0;
}

Submission Info

Judge Result