正题

题目链接:https://www.luogu.com.cn/problem/P4245

题目大意

两个多项式，求它们的乘积模\(p\)。

解题思路

方法好像挺多，我用的是最简单的一种就是，先定一个常数\(sqq\)（一般是\(\sqrt q\)），把一个项的数\(x\)拆成\(k*sqq+r\)。然后把\(F\)的\(k\)丢进\(A\)，\(r\)丢进\(B\)。\(G\)的\(k\)丢进\(C\)，\(r\)丢进\(D\)。

然后对于\(A*C\)的部分就是\(sqq^2\)的部分，\(A*D+B*C\)就是\(sqq\)，\(C*D\)就是\(1\)。这样下来要跑\(7\)次\(\text{FFT}\)，很慢但是能过，而且要开\(\text{long double}\)和预处理单位根不然会被卡精度。

有一个比较快的方法是变成两个复数多项式\(E[x]=A[x]+B[x]*i,F[x]=C[x]+D[x]*i\)（其中\(i\)表示\(\sqrt{-1}\)）。然后乘起来做一下公式就可以做到\(3\)次\(\text{FFT}\)。

还有一个就是不会被卡精度的\(\text{NTT}\)方法，就是找三个有原根的模数分别跑出来，然后用\(\text{CRT}\)合并，这个跑的次数多，但是因为是\(\text{NTT}\)所以常数和第一个差不多？

时间复杂度都是\(O(n\log n)\)就是常数有不同而已

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll long long

using namespace std;

const ll N=4e5+10,sqq=32768;

const long double Pi=acos(-1);

struct complex{

    long double x,y;

    complex (long double xx=0,long double yy=0)

    {x=xx;y=yy;return;}

}A[N],B[N],C[N],D[N];

complex operator+(complex a,complex b)

{return complex(a.x+b.x,a.y+b.y);}

complex operator-(complex a,complex b)

{return complex(a.x-b.x,a.y-b.y);}

complex operator*(complex a,complex b)

{return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}

ll n,m,p,F[N],G[N],H[N],r[N];

complex w[N];

void FFT(complex *f,ll op,ll n){

    for(ll i=0;i<n;i++)

        if(i<r[i])swap(f[i],f[r[i]]);

    for(ll p=2;p<=n;p<<=1){

        ll len=p>>1;

        for(ll k=0;k<n;k+=p)

            for(ll i=k;i<k+len;i++){

                complex tmp=w[n/len*(i-k)];

                if(op==-1)tmp.y=-tmp.y;

                complex tt=f[i+len]*tmp;

                f[i+len]=f[i]-tt;

                f[i]=f[i]+tt;

            }

    }

    if(op==-1){

        for(ll i=0;i<n;i++)

            f[i].x=(ll)(f[i].x/n+0.49);

    }

    return;

}

void MTT(ll *a,ll *b,ll *c,ll m,ll k){

    ll n=1;

    while(n<=m+k)n<<=1;

    for(ll i=0;i<n;i++)

        r[i]=(r[i>>1]>>1)|((i&1)?(n>>1):0);

    for(ll len=1;len<n;len<<=1)

        for(ll i=0;i<len;i++)

            w[n/len*i]=complex(cos(i*Pi/len),sin(i*Pi/len));

    for(ll i=0;i<m;i++)

        A[i].x=a[i]/sqq,B[i].x=a[i]%sqq;

    for(ll i=0;i<k;i++)

        C[i].x=b[i]/sqq,D[i].x=b[i]%sqq;

    FFT(A,1,n);FFT(B,1,n);FFT(C,1,n);FFT(D,1,n);

    complex t1,t2;

    for(ll i=0;i<n;i++){

        t1=A[i]*C[i];t2=B[i]*D[i];

        B[i]=A[i]*D[i]+B[i]*C[i];

        A[i]=t1;C[i]=t2;

    }

    FFT(A,-1,n);FFT(B,-1,n);FFT(C,-1,n);

    for(ll i=0;i<n;i++){

        (c[i]+=(ll)(A[i].x)*sqq%p*sqq%p)%=p;

        (c[i]+=(ll)(B[i].x)*sqq%p)%=p;

        (c[i]+=(ll)(C[i].x))%=p;

    }

    return;

}

signed main()

{

    scanf("%lld%lld%lld",&n,&m,&p);

    n++;m++;

    for(ll i=0;i<n;i++)scanf("%lld",&F[i]);

    for(ll i=0;i<m;i++)scanf("%lld",&G[i]);

    MTT(F,G,H,n,m);

    for(ll i=0;i<n+m-1;i++)

        printf("%lld ",(H[i]%p+p)%p);

}

巴特西

P4245-[模板]任意模数多项式乘法

正题

题目大意

解题思路

code

最新文章

热门文章