HDU 1402——A * B Problem Plus

灰太狼 2022-07-19 02:30 109阅读 0赞

题意：

给定a，b，求a\*b。

思路：

a,b的长度都为50000，直接模拟计算n\*m肯定超时，可以用快速傅里叶变化计算，然后再把相应的系数化简出来。

code：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    using namespace std;
    
    const double PI=acos(-1.0);
    struct complex
    {
        double l,r;
        complex(double ll=0.0,double rr=0.0){
            l=ll;r=rr;
        }
        complex operator +(const complex& B){
            return complex(l+B.l,r+B.r);
        }
        complex operator - (const complex& B){
            return complex(l-B.l,r-B.r);
        }
        complex operator *(const complex& B){
            return complex(l*B.l-r*B.r,l*B.r+B.l*r);
        }
    };
    
    /* * 进行FFT和IFFT前的反转变换。 * 位置i和j（i二进制反转后位置）互换 * len必须是2的幂 */
    void change(complex y[],int len){
        int i,j,k;
        for (int i=1,j=len/2;i<len-1;i++){
            if (i<j) swap(y[i],y[j]);
            k=len/2;
            while (j>=k){
                j-=k;
                k>>=1;
            }
            if (j<k) j+=k;
        }
    }
    /* * 做FFT * len必须为2^k形式， * on==1时是DFT，on==-1时是IDFT */
    void fft(complex y[],int len,int on){
        change(y,len);
        for (int h=2;h<=len;h<<=1){
            complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
            for (int j=0;j<len;j+=h){
                complex w(1,0);
                for (int k=j;k<j+h/2;k++){
                    complex u=y[k];
                    complex t=w*y[k+h/2];
                    y[k]=u+t;
                    y[k+h/2]=u-t;
                    w=w*wn;
                }
            }
        }
        if (on==-1){
            for (int i=0;i<len;i++){
                y[i].l/=len;
            }
        }
    }
    const int MAXN=200010;
    complex x1[MAXN],x2[MAXN];
    char s1[MAXN],s2[MAXN];
    int sum[MAXN];
    int main()
    {
        while (~scanf("%s%s",s1,s2)){
            int len1=strlen(s1);
            int len2=strlen(s2);
            int len=1;
            while (len<len1*2||len<len2*2) len<<=1;
            for (int i=0;i<len1;i++){
                x1[i]=complex(s1[len1-1-i]-'0',0);
            }
            for (int i=len1;i<len;i++){
                x1[i]=complex(0,0);
            }
            for (int i=0;i<len2;i++){
                x2[i]=complex(s2[len2-1-i]-'0',0);
            }
            for (int i=len2;i<len;i++) x2[i]=complex(0,0);
    
            fft(x1,len,1);
            fft(x2,len,1);
            for (int i=0;i<len;i++){
                x1[i]=x1[i]*x2[i];
            }
            fft(x1,len,-1);
    
            //化简和进位
            for (int i=0;i<len;i++){
                sum[i]=(int) (x1[i].l+0.5);
            }
            for(int i=0;i<len;i++){
                sum[i+1]+=(sum[i]/10);
                sum[i]%=10;
            }
            len=len1+len2-1;
            while (sum[len]<=0&&len>0) len--;
            for (int i=len;i>=0;i--){
                printf("%c",sum[i]+'0');
            }
            printf("\n");
        }
    }