FFT&NTT&多项式相关

打了FFT

感觉以后多项式不虚了 _滑稽

PS
关于详见没写完....

code

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

// pi = 3.14;

inline int read() {

    int x = 0,f = 1 ;

    char c = getchar();

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

    while(c <= '9' && c >= '0') x = x * 10 + c- '0' ,c = getchar ();

    return x *f;

}

const int maxn  = 5000007;

const double pi = acos(-1.0);

struct Complex {

    double x,y;

    Complex (double xx = 0,double yy = 0) { x = xx,y = yy; }

}f[maxn],g[maxn];

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

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

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

int n,m ;

int l,r[maxn];

int limit = 1;

void FFT (Complex * A,int type) {

    for(int i = 0;i < limit;i ++ )

        if(i < r[i]) std::swap(A[i],A[r[i]]); //get _迭代序列

    for(int mid = 1;mid < limit; mid <<= 1) {

        Complex wn  (cos(pi / mid) , type * sin(pi / mid));

        for(int R = mid << 1 ,j = 0;j < limit ; j += R) {

            Complex w(1,0);

            for(int k = 0;k < mid;k ++ ,w = w * wn) {

                Complex x = A[j + k] , y = w *A[j + mid + k];

                A[j + k] = x + y;

                A[j + mid + k] = x - y;

            }

        }

    }

}

int main() {

    n = read(), m = read();

    for(int i = 0;i <= n; ++ i) f[i] = read();

    for(int i = 0;i <= m; ++ i) g[i] = read();

    while(limit <= n + m) limit <<= 1,l ++;

    for(int i = 0;i < limit;i ++)

        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l-1));

    FFT(f,1);FFT(g,1);

    for(int i = 0;i <= limit;++ i) f[i] = f[i] * g[i];

    FFT(f,- 1);

    for(int i = 0;i <= n + m;++ i)

        printf("%d ",(int) (f[i].x / limit + 0.5));

    return 0;

}
巴特西

FFT&NTT&多项式相关

关于详见没写完....

code

最新文章

热门文章
