洛谷 P3803 多项式乘法

题目背景

这是一道FFT模板题

题目描述

给定一个n次多项式F(x)，和一个m次多项式G(x)。

请求出F(x)和G(x)的卷积。

输入输出格式

输入格式：

第一行2个正整数n,m。

接下来一行n+1个数字，从低到高表示F(x)的系数。

接下来一行m+1个数字，从低到高表示G(x))的系数。

输出格式：

一行n+m+1个数字，从低到高表示F(x)∗G(x)的系数。

输入输出样例

输入样例#1：

输出样例#1：

1 4 5 2

说明

保证输入中的系数大于等于 0 且小于等于9。

对于100%的数据： n, m \leq {10}^6n,m≤106, 共计20个数据点，2s。

数据有一定梯度。

空间限制：256MB

NTT和FFT有惊人的类似度hhh，总的说就是把单位根换成了原根。

最好是取一个形如p=k*2^x+1这样的质数p,这里x最好大一点。

然后在FFT里1的K次单位根是(cos(2*π/K),sin(2*π/K)) （一个复数）,而NTT里则是 g^((p-1)/K)。

dft的逆函数的话也类似,就是把g换成g^-1。

#include<bits/stdc++.h>

#define ll long long

#define maxn 3000005

#define ha 998244353

using namespace std;

const int ba=;

const int ni=ha/ba+;

inline int add(int x,int y){

    x+=y;

    if(x>=ha) x-=ha;

    return x;

}

inline int dec(int x,int y){

    x-=y;

    if(x<) x+=ha;

    return x;

}

inline int ksm(int x,int y){

    int an=;

    for(;y;y>>=,x=(ll)x*x%ha) if(y&) an=(ll)an*x%ha;

    return an;

}

int n,m,a[maxn],b[maxn];

int r[maxn],l,inv;

inline void fft(int *c,int f){

    for(int i=;i<n;i++) if(i<r[i]) swap(c[i],c[r[i]]);

    for(int i=;i<n;i<<=){

        int omega=(f==?ksm(ba,(ha-)/(i<<)):ksm(ni,(ha-)/(i<<)));

        for(int j=,p=i<<;j<n;j+=p){

            int now=;

            for(int k=;k<i;k++,now=(ll)now*omega%ha){

                int x=c[j+k],y=(ll)now*c[j+k+i]%ha;

                c[j+k]=add(x,y);

                c[j+k+i]=dec(x,y);

            }

        }

    }

    if(f==-) for(int i=;i<n;i++) c[i]=(ll)c[i]*inv%ha;

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++) scanf("%d",a+i);

    for(int i=;i<=m;i++) scanf("%d",b+i);

    m+=n;

    for(n=,l=;n<=m;n<<=) l++;

    for(int i=;i<n;i++) r[i]=(r[i>>]>>)|((i&)<<(l-));

    inv=ksm(n,ha-);

    fft(a,),fft(b,);

    for(int i=;i<n;i++) a[i]=(ll)a[i]*b[i]%ha;

    fft(a,-);

    for(int i=;i<=m;i++) printf("%d ",a[i]);

    puts("");

    return ;

}

巴特西

洛谷 P3803 多项式乘法

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章