FFT多项式乘法模板（HDU1402）

Bertha 。 2022-05-15 12:05 133阅读 0赞

## 这几天学了下FFT，入门推荐算法导论第三十章，话不多说，上板子。 ##

## 递归版： ##

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #pragma comment(linker, "/STACK:102400000,102400000")
    #include<unordered_map>
    #include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define pi acos(-1.0)
    typedef pair<int,int> PII;
    typedef complex<double> cd;
    const ll mod = 1e9+7;
    const int N = 2e5+10;
    
    ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    char a[N],b[N];
    cd A[N],B[N];
    int s[N];
    
    void fft(cd *x, int n, int type) {
        if(n == 1) return ;
        cd l[n>>1], r[n>>1];
        for (int i = 0; i < n; i += 2) {
            l[i>>1] = x[i];
            r[i>>1] = x[i+1];
        }
        fft(l, n>>1, type);
        fft(r, n>>1, type);
        cd wn(cos(2*pi/n), sin(type*2*pi/n)), w(1, 0), t;
        for(int i = 0; i < (n>>1); i++, w *= wn) {
            t = w*r[i];
            x[i] = l[i] + t;
            x[i+(n>>1)] = l[i] - t;
        }
    }
    
    int main() {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    
        while(cin>>a>>b) {
            int n=strlen(a),m=strlen(b);
            mst(A,0),mst(B,0),mst(s,0);
            for(int i=n-1;i>=0;i--) A[n-1-i]=a[i]-'0';
            for(int i=m-1;i>=0;i--) B[m-1-i]=b[i]-'0';
            m += n;
            for(n=1;n<m;n<<=1);
            fft(A,n,1);
            fft(B,n,1);
            for(int i=0;i<n;i++) A[i]*=B[i];
            fft(A,n,-1);
            for(int i=0;i<m;i++) {
                int t=(int)(A[i].real()/n+0.5);
                t += s[i];
                s[i] = t%10;
                s[i+1] += t/10;
            }
            int i;
            for(i=m;i>=1;i--) if(s[i]) break;
            for(;i>=0;i--) cout<<s[i];
            cout<<endl;
        }
        return 0;
    }

## 非递归版： ##

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #pragma comment(linker, "/STACK:102400000,102400000")
    #include<unordered_map>
    #include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define pi acos(-1.0)
    typedef pair<int,int> PII;
    typedef complex<double> cd;
    const ll mod = 1e9+7;
    const int N = 2e5+10;
    
    ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    char a[N],b[N];
    cd A[N],B[N];
    int s[N],R[N];
    
    void fft(cd *x,int n,int type) {
        for (int i = 0; i < n; i++) if(i < R[i]) swap(x[i], x[R[i]]);
        for (int i = 1; i < n; i <<= 1) {
            cd wn(cos(pi/i), type*sin(pi/i));
            for (int j = 0; j < n; j += i<<1) {
                cd w(1, 0);
                for (int k = 0; k < i; k++, w*=wn) {
                    cd X = x[j+k], Y = w*x[j+k+i];
                    x[j+k] = X+Y;
                    x[j+k+i] = X-Y;
                }
            }
        }
    }
    
    int main() {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        while(cin>>a>>b) {
            int n=strlen(a),m=strlen(b),L=0;
            mst(A,0),mst(B,0),mst(s,0),mst(R,0);
            for(int i=n-1;i>=0;i--) A[n-1-i]=a[i]-'0';
            for(int i=m-1;i>=0;i--) B[m-1-i]=b[i]-'0';
            m += n;
            for(n=1;n<m;n<<=1) L++;
            for (int i = 0; i < n; i++) {///二进制反转 蝴蝶操作
                R[i] = (R[i>>1]>>1) | ((i&1) << L-1);
            }
            fft(A,n,1);
            fft(B,n,1);
            for(int i=0;i<n;i++) A[i]*=B[i];
            fft(A,n,-1);
            for(int i=0;i<m;i++) {
                int t=(int)(A[i].real()/n+0.5);
                t += s[i];
                s[i] = t%10;
                s[i+1] += t/10;
            }
            int i;
            for(i=m;i>=1;i--) if(s[i]) break;
            for(;i>=0;i--) cout<<s[i];
            cout<<endl;
        }
        return 0;
    }