卷积 (f x g)(n)=∑{f(i)*g(n-i):i=...n}

多项式乘法就是一个系数向量的卷积

可以用FFT快速计算卷积

遇到和不是定值的情况可以反转一个向量

如本题反转a向量后

　　c[k]=∑(a[n-i-]*b[i-k]) k<=i<=n-

更换求和指标 i=i-k

　　c[k]=∑(a[n-i-k-]*b[i]) <=i<=n-k-

把-k-1消去，令t=n-k-

　　c[n-t-]=∑(a[t-i]*b[i]) <=i<=t

这样就是标准的卷积形式啦

以前的推导

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=(<<)+, INF=1e9;

const double PI=acos(-);

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

struct meow{

    double x, y;

    meow(double a=, double b=):x(a), y(b){}

};

meow operator +(meow a, meow b) {return meow(a.x+b.x, a.y+b.y);}

meow operator -(meow a, meow b) {return meow(a.x-b.x, a.y-b.y);}

meow operator *(meow a, meow b) {return meow(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);}

meow conj(meow a) {return meow(a.x, -a.y);}

typedef meow cd;

struct FFT{

    int n, rev[N];

    void ini(int lim) {

        n=; int k=;

        while(n<lim) n<<=, k++;

        for(int i=; i<n; i++) {

            int t=;

            for(int j=; j<k; j++) if(i&(<<j)) t |= (<<(k--j));

            rev[i]=t;

        }

    }

    void dft(cd *a, int flag) {

        for(int i=; i<n; i++) if(i<rev[i]) swap(a[i], a[rev[i]]);

        for(int l=; l<=n; l<<=) {

            int m=l>>;

            cd wn = meow(cos(*PI/l), flag*sin(*PI/l));

            for(cd *p=a; p!=a+n; p+=l) {

                cd w(, );

                for(int k=; k<m; k++) {

                    cd t = w*p[k+m];

                    p[k+m] = p[k] - t;

                    p[k] = p[k] + t;

                    w=w*wn;

                }

            }

        }

        if(flag==-) for(int i=; i<n; i++) a[i].x/=n;

    }

    void mul(cd *a, cd *b, int lim) {

        ini(lim);

        dft(a, ); dft(b, );

        for(int i=; i<n; i++) a[i]=a[i]*b[i];

        dft(a, -);

    }

}f;

int n;

cd a[N], b[N];

int main() {

    freopen("in","r",stdin);

    n=read();

    for(int i=; i<n; i++) a[i].x=read(), b[n--i].x=read();

    f.mul(a, b, n+n-);

    for(int i=n-; i<*n-; i++) printf("%d\n", int(a[i].x+0.5));

}