于是标题又暴露了一切
把b倒过来读进来，就变成了卷积（那是什么。。。？可以吃吗？）的形式
于是直接FFT一下就好了
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 P 15 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 ", (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 }
（p.s. Xs我回来啦！！！）