NTT简介

NTT简介算法用途多项式乘法系数取模。前置知识原根,FFT。原根阶:若(a,p)=1(a,p)=1(a,p)=1,则满足ar≡1(modp)ar≡1(modp)a^r\equiv1(\modp)的最小的rrr被称为aaa模ppp的阶。原根:如果r=φ(p)r=φ(p)r=\varphi(p),则称aaa为modpmodp\modp意义下的原根。原根有一个判定方法:把…

NTT简介"

算法用途

多项式乘法系数取模。

前置知识

原根,FFT。

原根

阶: (a,p)=1 ( a , p ) = 1 ,则满足 ar1(modp) a r ≡ 1 ( mod p ) 的最小的 r r 被称为
a

a
p p 的阶。

原根:如果
r=φ(p)

r = φ ( p )
,则称 a a
modp

mod p
意义下的原根。

原根有一个判定方法:把 p1 p − 1 质因数分解,若  i ∀   i ap1pip a p − 1 p i ≠ p ,则 a a
p

p
的原根。

不是所有数都有原根,但一般题目给你的都是有的。原根一般比较小,因此我们可以暴力枚举并用上面的方法判断。

NTT过程

根据欧拉定理的证明,原根有一个性质: a a
1

1
p1 p − 1 次模 p p 都不相同。类比FFT的单位复数根,可以令
an=ap1n

a n = a p 1 n
,然后直接把 a a 当成
w

w
来做就好啦。当然要说明它们的性质类似:

a2k2n=a2k(p1)/2n=ak(p1)/n=aknan/2an(an/2n)2=annak+n/2n=aknan/2n=akn a 2 n 2 k = a 2 k ( p − 1 ) / 2 n = a k ( p − 1 ) / n = a n k ∵ a n / 2 ≠ a n ( a n n / 2 ) 2 = a n n ∴ a n k + n / 2 = a n k a n n / 2 = − a n k



然后一样做就好了。

模板

洛谷P3803

因为每一位不会太大,用998244353等于没模,可以假设要模。

代码:

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1<<21
#define F inline
#define P 998244353
using namespace std;
int n,m,l,a[N],b[N],c[N],r[N],g[(N)+1][2];
F char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    return l==r?EOF:*l++;
}
F int _read(){
    int x=0; char ch=readc();
    while (!isdigit(ch)) ch=readc();
    while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc();
    return x;
}
F void writec(int x){ if (x>9) writec(x/10); putchar(x%10+48); }
F void _write(int x){ writec(x),putchar(' '); }
F int ksm(int a,int b){
    int ret=1;
    for (;b;b>>=1,a=1ll*a*a%P)
        if (b&1) ret=1ll*ret*a%P;
    return ret;
}
F void NTT(int *a,int f){
    for (int i=0;i<n;i++) if (i<r[i]) swap(a[i],a[r[i]]);
    for (int k=1;k<n;k<<=1){
        int wn=g[k<<1][f],w=1,x,y;
        for (int i=0;i<n;i+=k<<1,w=1)
            for (int j=0;j<k;j++,w=1ll*w*wn%P){
                x=a[i+j],y=1ll*w*a[i+j+k]%P;
                a[i+j]=(x+y)%P,a[i+j+k]=((x-y)%P+P)%P;
            }
    }
}
int main(){
    n=_read(),m=_read();
    for (int i=0;i<=n;i++) a[i]=_read();
    for (int i=0;i<=m;i++) b[i]=_read();
    for (m+=n,n=1;n<=m;n<<=1) l++;
    for (int i=1;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<l-1);
    for (int i=2;i<=n;i<<=1)
        g[i][1]=ksm(3,(P-1)/i),g[i][0]=ksm(g[i][1],P-2);
    NTT(a,1),NTT(b,1); for (int i=0;i<n;i++) c[i]=1ll*a[i]*b[i]%P;
    NTT(c,0); for (int i=0;i<n;i++) c[i]=1ll*c[i]*ksm(n,P-2)%P;
    for (int i=0;i<=m;i++) _write(c[i]); return 0;
}

今天的文章NTT简介分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/40091.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注