关于此题的hack

P1303 A*B Problem

虐lxl王子 @ 2020-05-26 20:47:03

#include<bits/stdc++.h>
#define n 131072
using namespace std;
struct apple
{
    double a,b;
    apple(double a=0,double b=0):a(a),b(b){}
    void operator+=(apple other)
    {
        a+=other.a;
        b+=other.b;
    }
    void operator-=(apple other)
    {
        a-=other.a;
        b-=other.b;
    }
    void operator*=(apple other)
    {
        double aa=a*other.a-b*other.b,bb=a*other.b+b*other.a;
        a=aa,b=bb;
    }
}ans[n],ans2[n],ans3[n],d1[n],d2[n],d[n],dd[n],f1[n],f2[n],cj[n+1];
char s1[n],s2[n];
int ff[n];
double pi=2*acos(-1);
void fft(apple d[],int nn,int cz,int cs)
{
apple cs2;
    if(nn==1)
    {
        ans[cs]=d[cs];
        return;
    }
    int bb=nn>>1;
    for(int i=0;i<bb;i++)dd[cs+i]=d[cs+(i<<1)];
    for(int i=0;i<bb;i++)dd[cs+bb+i]=d[cs+(i<<1|1)];
    for(int i=cs;i<cs+nn;i++)d[i]=dd[i];
    fft(d,bb,cz,cs);
    fft(d,bb,cz,cs+bb);
    for(int i=0;i<bb;i++)
    {
        cs2=cj[n/nn*i];
        apple ccs=cs2;
        if(cz==-1)
        {
            cs2.a=ccs.a/(ccs.a*ccs.a+ccs.b*ccs.b);
            cs2.b=-ccs.b/(ccs.a*ccs.a+ccs.b*ccs.b);
        }
        cs2*=ans[cs+bb+i];
        ans3[cs+i]=ans[cs+i];
        ans3[cs+i]+=cs2;
    }
    for(int i=bb;i<nn;i++)
    {
        cs2=cj[n/nn*i];
        apple ccs=cs2;
        if(cz==-1)
        {
            cs2.a=ccs.a/(ccs.a*ccs.a+ccs.b*ccs.b);
            cs2.b=-ccs.b/(ccs.a*ccs.a+ccs.b*ccs.b);
        }
        cs2*=ans[cs+i];
        ans3[cs+i]=ans[cs+i-bb];
        ans3[cs+i]+=cs2;
    }
    for(int i=cs;i<cs+nn;i++)ans[i]=ans3[i];
}
int main()
{
    cj[0]=apple(1,0),cj[1]=apple(cos(pi/n),sin(pi/n));
    for(int i=2;i<=n;i++)cj[i]=cj[i-1],cj[i]*=cj[1];
    int pppp;
    cin>>pppp;
    scanf("%s%s",s1,s2);
    int l1=strlen(s1),l2=strlen(s2);
    for(int i=0;i<l1;i++)f1[l1-i-1].a=s1[i]-'0';
    for(int i=0;i<l2;i++)f2[l2-i-1].a=s2[i]-'0';
    fft(f1,n,1,0);
    for(int i=0;i<n;i++)d1[i]=ans[i];
    fft(f2,n,1,0);
    for(int i=0;i<n;i++)d2[i]=ans[i];
    for(int i=0;i<n;i++)d1[i]*=d2[i],d[i]=d1[i];
    fft(d,n,-1,0);
    for(int i=0;i<n;i++)ff[i]=(ans[i].a+0.5)/n;
    for(int i=0;i<n;i++)ff[i+1]+=ff[i]/10,ff[i]%=10;
    int aa=0;
    for(int i=n-1;i>=0;i--)if(ff[i])
    {
        aa=i;
        break;
    }
    for(int i=aa;i>=0;i--)printf("%d",ff[i]);
    return 0;
}

这份代码在 darkbzoj 上WA了（bzoj2179），但在你谷上A了，能hack一下吗？

by IceYukino @ 2020-05-26 20:50:14

@liqingyang Orz他

by DeepSkyBlue__ @ 2020-05-26 20:50:27

id…

by IceYukino @ 2020-05-26 20:50:51

wmh？那一定要%了。

by 语文壬孑 @ 2020-05-26 20:50:59

奇怪的王子增加了！

by _5011_ @ 2020-05-26 20:51:47

@№ip

by 火石 @ 2020-05-26 20:53:09

stO wmh Orz

by liqingyang @ 2020-05-26 20:53:56

怀疑wmh会因为小号过多而......

by FZzzz @ 2020-05-26 20:59:58

@qym2008 啥210不是低保都没有吗虽然比我挂完之后高个一百多

by 虐lxl王子 @ 2020-05-26 21:00:20

@qym2008 @liqingyang 递归的不好看，我还用循环的吧

#include<bits/stdc++.h>
#define n 131072
using namespace std;
struct apple
{
    double a,b;
    apple(double a=0,double b=0):a(a),b(b){}
    void operator+=(apple other)
    {
        a+=other.a;
        b+=other.b;
    }
    void operator-=(apple other)
    {
        a-=other.a;
        b-=other.b;
    }
    void operator*=(apple other)
    {
        double aa=a*other.a-b*other.b,bb=a*other.b+b*other.a;
        a=aa,b=bb;
    }
}ans[n],ans3[n],d[n],d2[n],dd[n],cj[n+1];
char s1[n],s2[n];
int ff[n],tt[n];
double pi=2*acos(-1);
void fft(apple d[],int cz)
{
    for(int i=0;i<n;i++)dd[i]=d[tt[i]];
    for(int i=0;i<n;i++)d[i]=dd[i];
    for(int i=0;i<n;i++)ans[i]=d[i];
    apple cs2;
    for(int nn=2;nn<=n;nn<<=1)
    {
        for(int cs=0;cs<n;cs+=nn)
        {
            int bb=nn>>1;
            for(int i=0;i<bb;i++)dd[cs+(i<<1)]=d[cs+i];
            for(int i=0;i<bb;i++)dd[cs+(i<<1|1)]=d[cs+bb+i];
            for(int i=cs;i<cs+nn;i++)d[i]=dd[i];
            for(int i=nn-1;i>=bb;i--)
            {
                if(cz>0)cs2=cj[n/nn*i];
                else cs2=cj[n/nn*(nn-i)];
                cs2*=ans[cs+i];
                ans3[cs+i]=ans[cs+i-bb];
                ans3[cs+i]+=cs2;
            }
            for(int i=bb-1;i>=0;i--)
            {
                if(cz>0)cs2=cj[n/nn*i];
                else cs2=cj[n/nn*(nn-i)];
                cs2*=ans[cs+bb+i];
                ans3[cs+i]=ans[cs+i];
                ans3[cs+i]+=cs2;
            }
            for(int i=cs;i<cs+nn;i++)ans[i]=ans3[i];
        }
    }
}
int main()
{
int kkksb;
cin>>kkksb;
    tt[0]=0;
    int wz=1;
    for(int i=n;i>=2;i>>=1)
    {
        int pp=n/i;
        for(int j=wz;j<wz+pp;j++)tt[j]=tt[j-pp]+(i>>1);
        wz+=pp;
    }
    cj[0]=apple(1,0),cj[1]=apple(cos(pi/n),sin(pi/n));
    for(int i=2;i<=n;i++)cj[i]=cj[i-1],cj[i]*=cj[1];
    scanf("%s%s",s1,s2);
    int l1=strlen(s1),l2=strlen(s2);
    for(int i=0;i<l1;i++)d[l1-i-1].a=s1[i]-'0';
    for(int i=0;i<l2;i++)d2[l2-i-1].a=s2[i]-'0';
    fft(d,1);
    for(int i=0;i<n;i++)d[i]=ans[i];
    fft(d2,1);
    for(int i=0;i<n;i++)d[i]*=ans[i];
    fft(d,-1);
    for(int i=0;i<n;i++)ff[i]=(ans[i].a+0.5)/n;
    for(int i=0;i<n;i++)ff[i+1]+=ff[i]/10,ff[i]%=10;
    int aa=0;
    for(int i=n-1;i>=0;i--)if(ff[i])
    {
        aa=i;
        break;
    }
    for(int i=aa;i>=0;i--)printf("%d",ff[i]);
    return 0;
}

by dingcx @ 2020-05-26 21:01:04

高精用 FFT 的神仙……我都不会

上一页 | 下一页