关于此题的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 tangrunxi @ 2020-05-26 20:48:10

奇怪的王子增加了!


by bird_秒切橙题 @ 2020-05-26 20:48:20

a*b怎么这么难

cout<<a*b;

不就行了吗


by IceYukino @ 2020-05-26 20:48:34

\huge{lxl}!Orz


by xhQYm @ 2020-05-26 20:48:35

woc用FFT做可海星


by xhQYm @ 2020-05-26 20:48:58

@small_bird 高精


by IceYukino @ 2020-05-26 20:49:10

@small_bird Orz宁啊,看来宁写的编译器能够处理10^{10000}的情况


by liqingyang @ 2020-05-26 20:49:10

@small_bird 你不懂就别说,行不行?没看见人家虐lxl?


by ADay @ 2020-05-26 20:49:27

id危


by liqingyang @ 2020-05-26 20:49:44

@gqh_蒟蒻_or_大佬 C++自动转python


by xhQYm @ 2020-05-26 20:49:51

%wmh


| 下一页