1 /************************************************************** 2     Problem: 2194 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:2760 ms 7     Memory:21900 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13  14 #define complex P15 using namespace std;16 typedef double lf;17 const int N = 300005;18 const lf pi = acos(-1);19  20 struct complex {21     lf x, y;22     P() {}23     P(lf _x, lf _y) : x(_x), y(_y) {}24      25     inline P operator + (const P &X) const {26         return P(x + X.x, y + X.y);27     }28     inline P operator - (const P &X) const {29         return P(x - X.x, y - X.y);30     }31     inline P operator * (const P &X) const {32         return P(x * X.x - y * X.y, x * X.y + y * X.x);33     }34      35     inline void operator += (const P &X) {36         *this = *this + X;37     }38     inline void operator *= (const P &X) {39         *this = *this * X;40     }41 } x[N], y[N], w[2][N];42  43 int n, len;44 int a[N], b[N];45  46 inline int read() {47     int x = 0;48     char ch = getchar();49     while (ch < ‘0‘ || ‘9‘ < ch)50         ch = getchar();51     while (‘0‘ <= ch && ch <= ‘9‘) {52         x = x * 10 + ch - ‘0‘;53         ch = getchar();54     }55     return x;56 }57  58 void FFT(P *x, int len, int v) {59     int i, j, l;60     P tmp;61     for (i = j = 0; i < len; ++i) {62         if (i > j) swap(x[i], x[j]);63         for (l = len >> 1; (j ^= l) < l; l >>= 1);64     }65     for (i = 2; i <= len; i <<= 1)66         for (j = 0; j < len; j += i)67             for (l = 0; l < i >> 1; ++l) {68                 tmp = x[j + l + (i >> 1)] * w[v][len / i * l];69                 x[j + l + (i >> 1)] = x[j + l] - tmp;70                 x[j + l] += tmp;71             }72 }73  74 void work() {75     int i;76     for (len = 1; len < n << 1; len <<= 1);77     for (i = 0; i <= len; ++i)78         w[1][len -  i] = w[0][i] = P(cos(pi * 2 * i / len), sin(pi * 2 * i / len));79          80     for (i = 0; i < len; ++i)81         x[i] = P(a[i], 0), y[i] = P(b[i], 0);82     FFT(x, len, 0), FFT(y, len, 0);83      84     for (i = 0; i < len; ++i)85         x[i] *= y[i];86     FFT(x, len, 1);87  88     for (i = n - 1; i + 1 < n << 1; ++i)89         printf("%d\n", (int) round(x[i].x / len));90 }91  92 int main() {93     int i;94     n = read();95     for (i = 0; i < n; ++i)96         a[i] = read(), b[n - i - 1] = read();97     work();98     return 0;99 }