写完上一道题才意识到自己没有在博客里丢过FFT的模板……
这道题就是裸的多项式乘法，可以FFT，可以NTT，也可以用Karasuba（好像有人这么写没有T），也可以各种其他分治乘法乱搞…… 所以我就直接给板子了#include#include #define MAXN 300005#define DB double#define pi 3.14159265358struct cp { DB x, y; cp(){} cp(DB a, DB b):x(a), y(b){} cp operator + (const cp &r) const { return cp(x+r.x, y+r.y); } cp operator - (const cp &r) const { return cp(x-r.x, y-r.y); } cp operator * (const cp &r) const { return cp(x*r.x - y*r.y, x*r.y+y*r.x); }} a[MAXN], b[MAXN], tmp;inline void Swap(cp &a, cp &b) { tmp=a; a=b; b=tmp; }int n, m;inline void fft(cp *a, int f) { for(int i = 0, j = 0; i < n; ++ i) { if(i > j) Swap(a[i], a[j]); for(int l = (n>>1); (j^=l) < l; l >>= 1); } for(int i = 1; i < n; i <<= 1) { cp wn(cos(pi/i), f*sin(pi/i)); for(int j = 0; j < n; j += i<<1) { cp w(1, 0); for(int k = 0; k < i; ++ k, w = w * wn) { cp x = a[j + k], y = w * a[j + k + i]; a[j + k] = x + y; a[j + k + i] = x - y; } } } if(-1 == f) for(int i = 0; i < n; ++ i) a[i].x /= n;}int main() { scanf("%d%d", &n, &m); for(int i = 0; i <= n; ++ i) scanf("%lf", &a[i].x); for(int i = 0; i <= m; ++ i) scanf("%lf", &b[i].x); for(m = n+m, n = 1; n <= m; n <<= 1); fft(a, 1); fft(b, 1); for(int i = 0; i <= n; ++ i) a[i] = a[i] * b[i]; fft(a, -1); for(int i = 0; i <= m; ++ i) printf("%d ", (int)(a[i].x+0.1));}