1. 题目

LOJ 传送门=￣ω￣=
LUOGU 传送门=￣ω￣=

2. 题解

//这个递归方法过不了 LUOGU 的 $10^6$的数据，但能过 LOJ 的 $10^5$的数据。这个方法下面有蝶型算法的代码哦 QvQ

xzy 太弱了

连蝴蝶算法都不会

只能写递归实现的 fft

在 luogu 上（数据大 $10$倍）蜜汁RE

不应该递归最多也才 $log_2N$层吗，怎么 $10^6$就挂了。。。

QAQ.jpg

代码：

#include <bits/stdc++.h>
#define NS (400000)
using namespace std;
typedef complex<double> cpx;
int n,m;
cpx a[NS],b[NS],buff[NS];
void FFT(cpx*c,int n,int t)
{
    if(n==1)return;
    int mid=(n>>1);
    for(int i=0;i<mid;i++)buff[i]=c[i<<1],buff[i+mid]=c[i<<1|1];
    copy(buff,buff+n,c);
    cpx*c0=c,*c1=c+mid;
    FFT(c0,mid,t),FFT(c1,mid,t);
    cpx w(1,0),wn(cos(M_PI*2ll/n),t*sin(M_PI*2ll/n));
    for(int i=0;i<mid;i++,w*=wn)
        buff[i]=c0[i]+w*c1[i],buff[i+mid]=c0[i]-w*c1[i];
    copy(buff,buff+n,c);
}
int main()
{
    scanf("%d%d",&n,&m);
    double tmp;
    for(int i=0;i<=n;i++)scanf("%lf",&tmp),a[i].real(tmp);
    for(int i=0;i<=m;i++)scanf("%lf",&tmp),b[i].real(tmp);
    int len=1;while(len<=n+m)len<<=1;
    FFT(a,len,1),FFT(b,len,1);
    for(int i=0;i<=len;i++)a[i]*=b[i];
    FFT(a,len,-1);
    for(int i=0;i<=n+m;i++)printf("%d ",(int)(a[i].real()/len+0.5));
    return 0;
}

Update

蒟蒻终于学会了蝶型算法 QvQ

什么鬼蝶型，直接说二进制反转+迭代嘛，搞得好像很高端样的。

我发现算法与计算机科学存在装逼显得高大上的现象，使 OI 选手吓得不敢学 QvQ

代码：

#include <bits/stdc++.h>
#define NS (3000005)
using namespace std;
typedef complex<double> cpx;
int n,m,rev[NS];
cpx Fa[NS],Fb[NS];
void FFT(cpx*a,int lg,int t)
{
    int len=(1<<lg);
    for(int i=0;i<len;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
    for(int l=1;l<len;l<<=1)
        for(int s=0;s<len;s+=(l<<1))
        {
            cpx w(1,0),wn(cos(M_PI/l),t*sin(M_PI/l)),t0,t1;
            for(int i=s;i<s+l;i++,w*=wn)
                t0=a[i],t1=w*a[i+l],a[i]=t0+t1,a[i+l]=t0-t1;
        }
}
int main()
{
    scanf("%d%d",&n,&m);
    double tmp;
    for(int i=0;i<=n;i++)scanf("%lf",&tmp),Fa[i].real(tmp);
    for(int i=0;i<=m;i++)scanf("%lf",&tmp),Fb[i].real(tmp);
    int lg=0;while((1<<lg)<=n+m)lg++;
    for(int i=0;i<(1<<lg);i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
    FFT(Fa,lg,1),FFT(Fb,lg,1);
    for(int i=0;i<(1<<lg);i++)Fa[i]*=Fb[i];
    FFT(Fa,lg,-1);
    for(int i=0;i<=n+m;i++)printf("%d ",(int)(Fa[i].real()/(1<<lg)+0.5));
    return 0;
}