Submission #4499982

---

Source Code Expand

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cassert>
#include<ctime>
using namespace std;

#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define absd(x) (x<0?-(x):x)
#define pow2(x) ((x)*(x))
#define rep(i,n) for(int i=0; i<n; ++i)
#define repr(i,n) for(int i=n-1; i>=0; --i)
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define replr(i,s,n) for(int i=n; i>=s; --i)
#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)
#define repe(e,obj) for(auto e : obj)

#define SP << " " <<
#define COL << " : " <<
#define COM << ", " <<
#define ARR << " -> " <<
#define PNT(STR) cout << STR << endl
#define POS(X,Y) "(" << X << ", " << Y << ")"
#define DEB(A) " (" << #A << ") " << A
#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl
#define ALL(V) (V).begin(), (V).end()
#define INF 1000000007
#define INFLL 1000000000000000007LL
#define EPS 1e-9

typedef unsigned int uint;
typedef unsigned long ulong;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define P_TYPE int
typedef pair<P_TYPE, P_TYPE> P;
typedef pair<P, P_TYPE> PI;
typedef pair<P_TYPE, P> IP;
typedef pair<P, P> PP;
typedef priority_queue<P, vector<P>, greater<P> > pvqueue;

// x^n mod m
ll fast_pow(ll x, ll n, ll m) {
  ll r = 1;
  while(n) {
    if(n & 1) {
      r = (r * x) % m;
    }
    x = (x * x) % m;
    n >>= 1;
  }
  return r;
}

class FMT {
  int n;
  ll omega, omega_rev;
  ll p, n_rev;
  ll *tmp;

  // bit-traversal
  void bit_reverse(ll *d) {
    int i = 0;
    int ns = n >> 1, nss = n >> 2;
    for(int j = 0; j < ns; j += 2) {
      if(j < i) {
        swap(d[i], d[j]);
        swap(d[i+ns+1], d[j+ns+1]);
      }
      swap(d[i+1], d[j+ns]);
      int k = nss; i ^= k;
      while(k > i) {
        k >>= 1; i ^= k;
      }
    }
  }

  void fmt_calc(ll *a, ll base) {
    int n0 = n, m = 1;
    ll half = fast_pow(base, n/2, p);
    while(n0 > 1) {
      n0 >>= 1;
      ll w = fast_pow(base, n0, p), wk = 1;
      for(int j = 0; j < m; ++j) {
        for(int i = j; i < n; i += 2*m) {
          ll u = a[i], v = (a[i+m] * wk) % p;
          a[i] = (u + v) % p;
          a[i+m] = (u + (v*half) % p) % p;
        }
        wk = (wk * w) % p;
      }
      m <<= 1;
    }
  }
public:
  // p = a * n + 1 (n = 2^k)
  // -> omega^(p-1) ≡  1 (mod p)
  FMT(ll k, ll g, ll p) : p(p) {
    n = 1;
    while(k--) n <<= 1;


    assert((p-1) % n == 0);
    ll a = (p-1) / n;
    omega = fast_pow(g, a, p);
    omega_rev = fast_pow(omega, p-2, p);
    n_rev = fast_pow(n, p-2, p);
    tmp = new ll[n];
  }

  ~FMT() {
    delete tmp;
  }

  void fmt(ll *a, ll *result) {
    rep(i, n) result[i] = a[i];
    bit_reverse(result);
    fmt_calc(result, omega);
  }

  void ifmt(ll *a, ll *result) {
    rep(i, n) result[i] = (a[i] * n_rev) % p;
    bit_reverse(result);
    fmt_calc(result, omega_rev);
  }

  void convolute(ll *a, ll *b, ll *result) {
    fmt(a, tmp);
    fmt(b, result);
    for(int i = 0; i < n; ++i) tmp[i] = (result[i] * tmp[i]) % p;
    ifmt(tmp, result);
  }

  inline int size() const { return n; }
};

#define MOD 1004535809
int n, n0, k;
#define N 300000
ll a[N], b[N], c[N];

int main() {
  cin >> n;
  rep(i, n) cin >> a[i] >> b[i];
  n0 = 1; k = 0;
  while(n0 < n) k++, n0 <<= 1;
  FMT fmt(k+1, 3, MOD);

  fmt.convolute(a, b, c);
  cout << 0 << endl;
  rep(i, 2*n-1) {
    cout << c[i] << endl;
  }
  return 0;
}

Submission Info

Judge Result