题解 P1919 【【模板】A*B Problem升级版（FFT快速傅里叶）】

· · 个人记录

既没有py交易也没有FFT

魔鬼般的8位压行高精，你值得拥有

完全是压位高精模板，相信很简单易懂，不做过多解释，有问题私信找我，有价值的我会在评论区和私信同步回复（最好没有问题qwq）
用时: 2083ms / 内存: 1556KB 实测通过（真TM险）
当然，FFT题最好写FFT，本高精压位仅供参考。

希望管理员通过

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#define base 100000000
#define width 8
using namespace std;
struct Bignum
{
    long long data[20010],lg;
    Bignum (string t="")
    {
        memset(data,0,sizeof(data));
        int x=t.size()%width;
        lg=(bool)(x)+t.size()/width;
        for (int i=0;i<x;++i)
            data[lg]=(data[lg]<<3)+(data[lg]<<1)+t[i]-'0';
        for (int i=x;i<t.size();++i)
            data[lg-(i-x)/width-(bool)(x)]=(data[lg-(i-x)/width-(bool)(x)]<<3)+(data[lg-(i-x)/width-(bool)(x)]<<1)+t[i]-'0';
    }//毒瘤构造函数，压位之痛
    Bignum operator * (Bignum b)
    {
        Bignum tmp;
        tmp.lg=lg+b.lg;
        for (int i=1;i<=lg;++i)
            for (int j=1;j<=b.lg;++j)
            {
                tmp.data[i+j-1]+=data[i]*b.data[j];
                int pos=i+j-1;
                while (tmp.data[pos]>=base)
                    tmp.data[pos+1]+=tmp.data[pos]/base,tmp.data[pos]%=base,++pos;
            }
        while (!tmp.data[tmp.lg])
            --tmp.lg;
        return tmp;
    }
    void write()
    {
        printf("%lld",data[lg]);
        for (register int i=lg-1;i>=1;--i)
            printf("%08lld",data[i]);
        printf("\n");
    }//毒瘤输出，注意更改#define的压位参数时，printf仍需改为对应位数（如“%09lld”），同时注意不要爆了long long
};
int main()
{
    int n;
    string as,bs;
    cin>>n>>as>>bs;
    Bignum a(as),b(bs),c=a*b;
    c.write();
    return 0;
}//主程序短小精悍，Bignum模板又长又烦