Loading...

NTT 快速数论变换 学习笔记

check评论:0 条 remove_red_eye浏览量:661 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-01-22

qaq
现在就差不多学了个板子

我们将$FFT$中的单位根换成原根以减小精度误差

然后其他和$FFT$基本一样啊qaq

就是最后除以$limit$改成乘$limit%mod$的逆元

做多项式乘法是可以将$mod$设为$998244353$,他的原根是$3$

其他讲解先鸽了qaq

代码如下

#include <bits/stdc++.h>
using namespace std;
long long a[4000040],b[4000040];
int n,m,limit=1,l,r[4000040];
#define mod 998244353
#define ge 3
long long ksm(long long x,int f)
{
    long long qaq=1;
    while(f)
    {
        if(f&1)
        {
            qaq*=x;
            qaq%=mod;
        }
        x*=x;
        x%=mod;
        f>>=1;
    }
    return qaq;
} 
void NTT(long long n[],int flag)
{
    for(int i=0;i<=limit;i++)
    {
        if(i<r[i])
        {
            swap(n[i],n[r[i]]);
        }
    }
    for(int mid=1;mid<limit;mid<<=1)
    {
        long long wn=ksm(ge,flag==1?(mod-1)/(mid<<1):(mod-1-((mod-1)/(mid<<1))));
        for(int r=(mid<<1),i=0;i<limit;i+=r)
        {
            long long w=1;
            for(int k=0;k<mid;k++,w=w*wn%mod)
            {
                long long x=n[i+k],y=w*n[i+mid+k]%mod;
                n[i+k]=(x+y)%mod,n[i+mid+k]=(x-y+mod)%mod;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    for(int i=0;i<=m;i++)
    {
        scanf("%lld",&b[i]);
    }
    while(limit<=n+m)
    {
        limit<<=1;
        l++;
    }
    for(int i=0;i<=limit;i++)
    {
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    }
    NTT(a,1);
    NTT(b,1);
    for(int i=0;i<=limit;i++)
    {
        a[i]=a[i]*b[i]%mod;
    }
    NTT(a,0);
    long long inv=(ksm(limit,mod-2)+mod)%mod;
    for(int i=0;i<limit;i++)
    {
        a[i]=(a[i]*inv+mod)%mod;
    }
    for(int i=0;i<=n+m;i++)
    {
        printf("%lld ",a[i]);
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名