P1919 【模板】A*B Problem升级版 /// FFT模板

题目大意：

给定l，输入两个位数为l的数A B

输出两者的乘积

FFT讲解这个讲解蛮好的就是讲解里面贴的模板是错误的

struct cpx {

    double x,y;

    cpx(double _x=0.0,double _y=0.0) {

        x=_x; y=_y;

    }

    cpx operator -(const cpx &b) const {

        return cpx(x-b.x,y-b.y);

    }

    cpx operator +(const cpx &b) const {

        return cpx(x+b.x,y+b.y);

    }

    cpx operator *(const cpx &b) const {

        return cpx(x*b.x-y*b.y,x*b.y+y*b.x);

    }

};

void change(cpx a[],int len) /// 位置互换 len必须是2的幂

{

    for(int i=,j=len/;i<len-;i++) {

        if(i<j) swap(a[i],a[j]);

        int k=len/;

        while(j>=k) j-=k, k>>=;

        if(j<k) j+=k;

    }

}

#define PI acos(-1)

void fft(cpx a[],int len,int on)/// len必须是2的幂 on为1时dft -1时idft

{

    change(a,len);

    for(int i=;i<len;i <<= ) {

        cpx wn(cos(PI/i),on*sin(PI/i));

        for(int j=;j<len;j+=(i<<)) {

            cpx w(,);

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

                cpx u=a[j+k], v=w*a[j+k+i];

                a[j+k]=u+v, a[j+k+i]=u-v;

            }

        }

    }

    if(on==-) {

        for(int i=;i<len;i++)

            a[i].x/=len;

    }

}

FFT模板1

题解讲解

struct cpx {

    double x,y;

    cpx(double _x=0.0,double _y=0.0) {

        x=_x; y=_y;

    }

    cpx operator - (const cpx &b)const {

        return cpx(x-b.x,y-b.y);

    }

    cpx operator + (const cpx &b)const {

        return cpx(x+b.x,y+b.y);

    }

    cpx operator * (const cpx &b)const {

        return cpx(x*b.x-y*b.y,x*b.y+y*b.x);

    }

};

void fft(cpx a[],int on)

{

    for(int i=;i<len;i++)

        if(i<r[i]) swap(a[i],a[r[i]]);

    for(int i=;i<len;i<<=) {

        cpx wn(cos(PI/i),on*sin(PI/i));

        for(int j=;j<len;j+=(i<<)) {

            cpx w(,);

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

                cpx u=a[j+k], v=w*a[j+k+i];

                a[j+k]=u+v, a[j+k+i]=u-v;

            }

        }

    }

}

int main()

{

    ......

    while(len<d*) len <<= , l++; // 将长度补到2的幂

    for(int i=;i<len;i++)

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

    ......

}

FFT模板2

这题是把两个数看成

A=a1*10^0+a2*10^1+a3*10^2...+al*10^(l-1)

B=b1*10^0+b2*10^1+b3*10^2...+bl*10^(l-1)

的形式

这样就变成了多项式相乘

#include <bits/stdc++.h>

#define PI acos(-1)

#define MAXN 300004

using namespace std;

struct cpx{

    double x,y;

    cpx(double _x=0.0,double _y=0.0) {

        x=_x; y=_y;

    }

    cpx operator-(const cpx &b)const {

        return cpx(x-b.x,y-b.y);

    }

    cpx operator+(const cpx &b)const {

        return cpx(x+b.x,y+b.y);

    }

    cpx operator*(const cpx &b)const {

        return cpx(x*b.x-y*b.y,x*b.y+y*b.x);

    }

}x1[MAXN/], x2[MAXN/];

char str1[MAXN/], str2[MAXN/];

int sum[MAXN], l;

void change(cpx a[],int len) /// 位置互换 len必须是2的幂

{

    for(int i=,j=len/;i<len-;i++) {

        if(i<j) swap(a[i],a[j]);

        int k=len/;

        while(j>=k) {

            j-=k, k >>= ;

        }

        if(j<k) j+=k;

    }

}

void fft(cpx a[],int len,int on)/// len必须是2的幂 on为1时dft -1时idft

{

    change(a,len);

    for(int i=;i<len;i <<= ) {

        cpx wn(cos(PI/i),on*sin(PI/i));

        for(int j=;j<len;j+=(i<<)) {

            cpx w(,);

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

                cpx u=a[j+k], t=w*a[j+k+i];

                a[j+k]=u+t, a[j+k+i]=u-t;

            }

        }

    }

    if(on==-) {

        for(int i=;i<len;i++)

            a[i].x/=len;

    }

}

int main()

{

    while(~scanf("%d",&l)) {

        scanf("%s%s",str1,str2);

        int len=;

        while(len<l*) len <<= ; // 将长度补到2的幂

        for(int i=;i<l;i++)

            x1[i]=cpx(str1[l--i]-'',),

            x2[i]=cpx(str2[l--i]-'',);

        for(int i=l;i<len;i++)

            x1[i]=x2[i]=cpx(,); // 不足补0

        fft(x1,len,); fft(x2,len,); /// dft转为点值表达

        for(int i=;i<len;i++) x1[i]=x1[i]*x2[i]; // 计算

        fft(x1,len,-); /// idft转为系数表达

        for(int i=;i<len;i++)

            sum[i]=(int)(x1[i].x+0.1); // 四舍五入

        for(int i=;i<len;i++)

            sum[i+]+=sum[i]/, sum[i]%=; // 进制

        while(sum[len]== && len>) len--; // 去前导0

        for(int i=len;i>=;i--)

            printf("%d",sum[i]); printf("\n");

    }

    return ;

}

两种模板的细节区别在于

（2）在四舍五入时除len ，而（1）是在FFT中判断开关on再除len

#include <bits/stdc++.h>

#define PI acos(-1.0)

const int MAXN=;

using namespace std;

struct cpx {

    double x,y;

    cpx(double _x=0.0,double _y=0.0) {

        x=_x; y=_y;

    }

    cpx operator - (const cpx &b)const {

        return cpx(x-b.x,y-b.y);

    }

    cpx operator + (const cpx &b)const {

        return cpx(x+b.x,y+b.y);

    }

    cpx operator * (const cpx &b)const {

        return cpx(x*b.x-y*b.y,x*b.y+y*b.x);

    }

}x1[MAXN], x2[MAXN];

int n, m, len=;

int l, r[MAXN], sum[MAXN];

char str1[MAXN],str2[MAXN];

void fft(cpx a[],int on)

{

    for(int i=;i<len;i++)

        if(i<r[i]) swap(a[i],a[r[i]]);

    for(int i=;i<len;i<<=) {

        cpx wn(cos(PI/i),on*sin(PI/i));

        for(int j=;j<len;j+=(i<<)) {

            cpx w(,);

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

                cpx u=a[j+k], v=w*a[j+k+i];

                a[j+k]=u+v, a[j+k+i]=u-v;

            }

        }

    }

}

int main()

{

    int d;

    while(~scanf("%d",&d)) {

        scanf("%s%s",str1,str2);

        while(len<d*) len <<= , l++; // 将长度补到2的幂

        for(int i=;i<d;i++)

            x1[i]=cpx(str1[d--i]-'',),

            x2[i]=cpx(str2[d--i]-'',);

        for(int i=;i<len;i++)

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

        fft(x1,); fft(x2,); /// dft转为点值表达

        for(int i=;i<len;i++) x1[i]=x1[i]*x2[i]; // 计算

        fft(x1,-); /// idft转为系数表达

        for(int i=;i<len;i++)

            sum[i]=(int)(x1[i].x/len+0.1); // 四舍五入

        for(int i=;i<len;i++)

            sum[i+]+=sum[i]/, sum[i]%=; // 进制

        while(sum[len]== && len>) len--; // 去前导0

        for(int i=len;i>=;i--)

            printf("%d",sum[i]); printf("\n");

    }

    return ;

}

巴特西

P1919 【模板】A*B Problem升级版 /// FFT模板

最新文章

热门文章