(未完待续)
$\texttt{NTT}$ 解决的是多项式乘法带模数的情况,可以说有些受模数的限制,数也比较大。但是速度快且不会有精度损失。
前置知识
未完待续。
生成子群
子群:群 $(S,\oplus),(S’,\oplus)$,满足 $S’\subset S$,则 $(S’,\oplus)$ 是 $$(S,\oplus)$ 的子群。
拉格朗日定理:$|S’|\mid|S|$ 证明需要用到陪集,得到陪集大小等于子群大小,每个陪集要么不相交要么相等,所有陪集的并是集合 $S$,那么显然成立。
生成子群:$a\in S$ 的生成子群 $\left<a\right>=\{a^{(k)},k\geq 1\}$,$a$ 是 $\left<a\right>$ 的生成元。
原根
快速数论变换 NTT
把 $\texttt{FFT}$ 中的 单位元 变换成 原根,就得到了 $\texttt{NTT}$。
简单代码实现
inline void NTT(reg ll a[],reg int f){ for(reg int i=0;i<limit;++i) if(i<r[i]) swap(a[i],a[r[i]]); for(reg int i=1;i<limit;i<<=1){ reg ll w=pow(f==1?g:invg,(p-1)/(i<<1),p); for(reg int j=0;j<limit;j+=(i<<1)){ reg ll e=1; for(reg int k=0;k<i;++k,e=(e*w)%p){ reg ll x=a[j+k],y=e*a[j+k+i]%p; a[j+k]=(x+y)%p,a[j+k+i]=(x-y+p)%p; } } } return; }
I have been surfing online more than 3 hours nowadays, yet I by no means found
any attention-grabbing article like yours. It is pretty value enough for me.
Personally, if all webmasters and bloggers made
excellent content material as you probably did, the web can be much more useful than ever before.