算法用途
多项式乘法系数取模。
前置知识
原根,FFT。
原根
阶:若 (a,p)=1 ( a , p ) = 1 ,则满足 ar≡1(modp) a r ≡ 1 ( mod p ) 的最小的 r r 被称为
a
模 p p 的阶。
原根:如果
r=φ(p)
,则称 a a 为
modp
意义下的原根。
原根有一个判定方法:把 p−1 p − 1 质因数分解,若 ∀ i ∀ i , ap−1pi≠p a p − 1 p i ≠ p ,则 a a 为
p
的原根。
不是所有数都有原根,但一般题目给你的都是有的。原根一般比较小,因此我们可以暴力枚举并用上面的方法判断。
NTT过程
根据欧拉定理的证明,原根有一个性质: a a 的
1
到 p−1 p − 1 次模 p p 都不相同。类比FFT的单位复数根,可以令
an=ap−1n
,然后直接把 a a 当成
w
来做就好啦。当然要说明它们的性质类似:
然后一样做就好了。
模板
洛谷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