spoj Fast Multiplication

时间：2023-03-09 00:22:50
spoj Fast Multiplication

题意：乘法

要用nlogn的fft乘法。

//#pragma comment(linker,"/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<vector>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<set>

#include<algorithm>

#include <stack>

using namespace std;

typedef long long lon;

//#define ll long long

//#define inf 1000000000

//#define mod 1000000007

#define N 350000

#define fo(i,a,b) for(i=a;i<=b;i++)

#define fd(i,a,b) for(i=a;i>=b;i--)

const lon SZ=,INF=0x7FFFFFFF;

const double pi = acos(-);

char s1[N>>],s2[N>>];

double rea[N],ina[N],reb[N],inb[N],ret[N],intt[N];

int i,len1,len2,lent,lenres,len;

int res[N>>];

void Swap(double &x,double &y)

{double t = x; x = y; y = t;}

int rev(int x,int len)

{

    int ans = ,i;

    fo(i,,len) {ans<<=; ans|=x&; x>>=;}

    return ans;

}

void FFT(double *reA,double *inA,int n,int flag)

{

    int s,i,j,k; int lgn = log((double)n) / log((double));

    fo(i,,n-)//数组重排

        {

            j = rev(i,lgn);

            if (j > i) {Swap(reA[i],reA[j]); Swap(inA[i],inA[j]);}

        }

    fo(s,,lgn)

        {

            int m = ( << s);

            double reWm = cos(*pi/m) , inWm = sin(*pi/m);

            if (flag) inWm = -inWm;

            for (k = ;k < n; k += m)

                {

                    double reW = 1.0 , inW = 0.0;

                    fo(j,,m/-)

                        {

                            int tag = k + j + m / ;

                            double reT = reW * reA[tag] - inW * inA[tag];

                            double inT = reW * inA[tag] + inW * reA[tag];

                            double reU = reA[k+j] , inU = inA[k+j];

                            reA[k+j] = reU + reT; inA[k+j] = inU + inT;

                            reA[tag] = reU - reT; inA[tag] = inU - inT;

                            double reWt = reW * reWm - inW * inWm;

                            double inWt = reW * inWm + inW * reWm;

                            reW = reWt; inW = inWt;

                        }

                }

        }

}

void work()

{

    scanf(" %s %s",s1,s2);

        memset(res,  , sizeof(res));

        memset(rea,  , sizeof(rea));

        memset(ina,  , sizeof(ina));

        memset(reb,  , sizeof(reb));

        memset(inb,  , sizeof(inb));

    len1 = strlen(s1); len2 = strlen(s2);

    lent = (len1 > len2 ? len1 : len2); len = ;

    while (len < lent) len <<= ; len <<= ;

    fo(i,,len-)

        {

            if (i < len1) rea[i] = (double) s1[len1-i-] - '';

            if (i < len2) reb[i] = (double) s2[len2-i-] - '';

            ina[i] = inb[i] = 0.0;

        }

    FFT(rea,ina,len,); FFT(reb,inb,len,);//求出a、b的点值表示法

    fo(i,,len-)//求出c的点值表示法

        {

            //printf("%.5lf %.5lf\n",rea[i],ina[i]);

            double rec = rea[i] * reb[i] - ina[i] * inb[i];

            double inc = rea[i] * inb[i] + ina[i] * reb[i];

            rea[i] = rec; ina[i] = inc;

        }

    FFT(rea,ina,len,);

    fo(i,,len-) {rea[i] /= len; ina[i] /= len;}

    fo(i,,len-) res[i] = (int)(rea[i] + 0.5);

    fo(i,,len-) res[i+] += res[i] /  , res[i] %= ;

    lenres = len1 + len2 + ;

    while (res[lenres] ==  && lenres > ) lenres--;

    fd(i,lenres,) printf("%d",res[i]); printf("\n");

} 

int main()

{

    std::ios::sync_with_stdio();

    //freopen("d:\\1.txt","w",stdout);

    lon casenum;

    cin>>casenum;

    for(lon time=;time<=casenum;++time)

    //for(;scanf("%d",&n)!=EOF;)

    {

        work();

        //cout<<mul(m1,m2)<<endl;

    }

    return ;

}

相关文章