《人间油物》

在利用卷积使得各项相乘的时候,由于顺序会被交换,所以b数组要倒序输入,可以看成是两个卷积之间的配对.

画个图就懂了~

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int N=4e6+5;
const int mod=998244353;
const double pi=acos(-1);
 
struct cp{
    double x,y;
    cp(){x=0,y=0;}
    cp(double X,double Y){x=X,y=Y;};
}f[N],g[N],ans[N];
 
cp operator + (cp A,cp B)
{
    return cp(A.x+B.x,A.y+B.y);
}
 
cp operator - (cp A,cp B)
{
    return cp(A.x-B.x,A.y-B.y);
}
 
cp operator * (cp A,cp B)
{
    return cp(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);
}
 
int b=0;
int rev[N];
int now[N];
void fft(int n,cp *a,int op)
{
    for(int i=0;i<n;i++)
        if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int len=1;len<=n/2;len<<=1)//枚举分治半长度.
    {
        cp w1=cp(cos(pi/len),op*sin(pi/len));
        for(int i=0;i<=n-(len<<1);i+=(len<<1))
        {
            cp w=cp(1,0);
            for(int j=0;j<len;j++)
            {
                cp x=a[i+j];cp y=w*a[i+j+len];
                a[i+j]=x+y;
                a[i+j+len]=x-y;
                w=w*w1;
            }
        }
    }
}
 
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)    scanf("%lf",&f[i].x);
    for(int i=0;i<n;i++)    scanf("%lf",&g[n-i-1].x);
    int k=1;
    while(k<n*2-1)    k<<=1,b++;
    for(int i=1;i<=k;i++)
        rev[i]=(rev[i>>1]>>1)+((i&1)<<(b-1));
    fft(k,f,1);
    fft(k,g,1);
    for(int i=0;i<k;i++)
        ans[i]=f[i]*g[i];
    fft(k,ans,-1);
    int res=0;
    for(int i=0;i<n*2-1;i++)
    {
        now[i%n]+=(int)(ans[i].x/k+0.5);
    }
    for(int i=0;i<n;i++)
    {
        res=max(res,now[i]);
    }
    cout<<res<<'\n';
    return 0;
}