FFT 留个板子（后续可能还有FWT，NNT等）

心已赠人 2023-03-01 13:47 13阅读 0赞

用于解决多项式乘法（朴素N^2，fft nlogn）

洛谷 多项式乘法：[https://www.luogu.com.cn/problem/list?keyword=fft&page=1][https_www.luogu.com.cn_problem_list_keyword_fft_page_1]

#include<bits/stdc++.h>
    #define N 8000005
    using namespace std;
    const double pi = acos(-1.0);
    struct complexx{
        double x, y;
        complexx(double xx = 0, double yy = 0) {x = xx, y = yy;}
    }a[N];
    double coss[N], sinn[N];
    int rev[N];
    complexx operator + (complexx a, complexx b) {return complexx(a.x + b.x, a.y + b.y);}
    complexx operator - (complexx a, complexx b) {return complexx(a.x - b.x, a.y - b.y);}
    complexx operator * (complexx a, complexx b) {return complexx(a.x * b.x - a.y * b.y, a.y * b.x + a.x * b.y);}
    void fft(int len, complexx *a, int o){
    
        for(int i = 0; i <= len; i ++) if(i < rev[i]) swap(a[i], a[rev[i]]);
        for(int j = 1; j < len; j <<= 1){//j枚举的是合并区间长度的一半，即把两个长度为j的序列合成一个长度为2*j的序列
            complexx wn = complexx(coss[j], o * sinn[j]);
            for(int k = 0; k < len; k += (j << 1)){//k为当前处理的区间的开头
                complexx w0 = complexx(1, 0);
                for(int i = 0; i < j; i ++, w0 = w0 * wn){//i为对应位
                    complexx X = a[i + k], Y = w0 * a[i + j + k];
                    a[i + k] = X + Y;
                    a[i + k + j] = X - Y;//合并
                }
            }
        }
    }
    int n, m;
    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", &a[i].y);
        int len = 1, l = 0;
        for(;len <= n + m; len <<= 1, l ++);
        for(int i = 0; i <= len; i ++) rev[i] = (rev[i >> 1] >> 1) | ((i&1) << (l - 1));//rev[i]位将i按二进制后的值（类似数位dp的思想）
        for(int i = 1; i <= len; i <<= 1) coss[i] = cos(pi / i), sinn[i] = sin(pi / i);//注意这里pi不用乘2
        fft(len, a, 1);
        for(int i = 0; i <= len; i ++)
            a[i] = a[i] * a[i];
        fft(len, a, -1);
        for(int i = 0; i <= n + m; i ++) printf("%.0f ", a[i].y / 2 / len + 0.49);
        return 0;
    }

洛谷 A\*B [https://www.luogu.com.cn/problem/P1919][https_www.luogu.com.cn_problem_P1919]

就是上面那个板子改改的事情，这个板子还可以用于大数相乘，时间复杂度为（len\*loglen）比朴素的n^2好很多

#include<bits/stdc++.h>
    #define N 8000005
    using namespace std;
    const double pi = acos(-1.0);
    struct complexx{
        double x, y;
        complexx(double xx = 0, double yy = 0) {x = xx, y = yy;}
    }a[N];
    double coss[N], sinn[N];
    int rev[N];
    complexx operator + (complexx a, complexx b) {return complexx(a.x + b.x, a.y + b.y);}
    complexx operator - (complexx a, complexx b) {return complexx(a.x - b.x, a.y - b.y);}
    complexx operator * (complexx a, complexx b) {return complexx(a.x * b.x - a.y * b.y, a.y * b.x + a.x * b.y);}
    void fft(int len, complexx *a, int o){
    
        for(int i = 0; i <= len; i ++) if(i < rev[i]) swap(a[i], a[rev[i]]);
        for(int j = 1; j < len; j <<= 1){//j枚举的是合并区间长度的一半，即把两个长度为j的序列合成一个长度为2*j的序列
            complexx wn = complexx(coss[j], o * sinn[j]);
            for(int k = 0; k < len; k += (j << 1)){//k为当前处理的区间的开头
                complexx w0 = complexx(1, 0);
                for(int i = 0; i < j; i ++, w0 = w0 * wn){//i为对应位
                    complexx X = a[i + k], Y = w0 * a[i + j + k];
                    a[i + k] = X + Y;
                    a[i + k + j] = X - Y;//合并
                }
            }
        }
    }
    int n, m;
    int main(){
        //scanf("%d%d", &n, &m);
        string s1,s2;
        cin>>s1>>s2;
        n=s1.size()-1;
        m=s2.size()-1;
        for(int i = 0; i <= n; i ++)a[i].x=s1[n-i]-'0';
        for(int i = 0; i <= m; i ++) a[i].y=s2[m-i]-'0';
        int len = 1, l = 0;
        for(;len <= n + m; len <<= 1, l ++);
        for(int i = 0; i <= len; i ++) rev[i] = (rev[i >> 1] >> 1) | ((i&1) << (l - 1));//rev[i]位将i按二进制后的值（类似数位dp的思想）
        for(int i = 1; i <= len; i <<= 1) coss[i] = cos(pi / i), sinn[i] = sin(pi / i);//注意这里pi不用乘2
        fft(len, a, 1);
        for(int i = 0; i <= len; i ++)
            a[i] = a[i] * a[i];
        fft(len, a, -1);
        for(int i = 0; i <= n + m; i ++) a[i].x= int(a[i].y / 2 / len + 0.49);
         //for(int i = 0; i <= n + m; i ++) cout<<a[i].x<<' ';cout<<endl;
        for(int i = 1; i <= n + m; i ++) a[i].x+=int (a[i-1].x)/10;
        //for(int i = 0; i <= n + m; i ++) cout<<a[i].x<<' ';cout<<endl;
        for(int i = 0; i <n + m; i ++) a[i].x=int(a[i].x)%10;
        //for(int i=n+m;i>=0;i--) cout<<a[i].x<<' ';cout<<endl;
        cout<<int(a[n+m].x);
        for(int i=n+m-1;i>=0;i--){cout<<int(a[i].x)%10;}cout<<endl;
        return 0;
    }

[https_www.luogu.com.cn_problem_list_keyword_fft_page_1]: https://www.luogu.com.cn/problem/list?keyword=fft&page=1
[https_www.luogu.com.cn_problem_P1919]: https://www.luogu.com.cn/problem/P1919