Cptraser/ 三月 4, 2019/ 2019.3/ 0 comments

FFT精度可能会炸掉时,我们就需要NTT了。

此时就需要用原根来代替复数了。

原根

m是正整数,a是整数,若am的阶等于\varphi(m),则称a为模m的一个原根

原根满足以下FFT同样满足的性质:
* 对于所有\omega_{n}^{t}(0\leq t\leq n-1)均不同,若P为素数,设gP的原根则g^{i}\ mod\ P(1<g<P,0<i<P)的结果两两不同。(原根的定义)
* \omega_{2n}^{2k}=\omega_{n}^{k}
* \omega_{n}^{k+\frac{n}{2}}=-\omega_{n}^{k}(由费马小定理和第一条可得)
* 1+\omega_{n}^{k}+(\omega_{n}^{k})^2+...+(\omega_{n}^{k})^{n-1}=0(由上一条和FFT逆变换定理可得)

最终我们可得:

    \[\omega_{n}=g^{\frac{p-1}{n}}\ mod\ p\]

然后将FFT中的w_{n}全部替换即可。
p=998244353时原根为3

板题传送门

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

void read(int &x){char c;for(;!isdigit(c=getchar()););for(x=c-48;isdigit(c=getchar());x=(x<<1)+(x<<3)+c-48);}
void read(long long &x){char c;for(;!isdigit(c=getchar()););for(x=c-48;isdigit(c=getchar());x=(x<<1)+(x<<3)+c-48);}

const int Maxn=3e6+5,Mod=998244353,G=3,InvG=332748118;

int N,M,limit=1,L,r[Maxn];
long long A[Maxn],B[Maxn];

long long Ksm(long long x,long long y){
    long long res=1;for(;y;y>>=1,x=x*x%Mod)if(y&1)res=res*x%Mod;return res;
}

void NTT(long long *A,int Opt){
    for(int i=0;i<limit;i++)if(i<r[i])swap(A[i],A[r[i]]);
    for(int Mid=1;Mid<limit;Mid<<=1){
        long long Wn=Ksm(Opt==1?G:InvG,(Mod-1)/(Mid<<1));
        for(int j=0;j<limit;j+=(Mid<<1)){
            long long w=1;
            for(int k=0;k<Mid;k++,w=(w*Wn)%Mod){
                int x=A[j+k],y=w*A[j+k+Mid]%Mod;
                A[j+k]=(x+y)%Mod;
                A[j+k+Mid]=(x-y+Mod)%Mod;
            }
        }
    }
}

int main()
{
    read(N),read(M);
    for(int i=0;i<=N;i++)read(A[i]),A[i]=(A[i]+Mod)%Mod;
    for(int i=0;i<=M;i++)read(B[i]),B[i]=(B[i]+Mod)%Mod;
    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,-1);
    long long Inv=Ksm(limit,Mod-2);
    for(int i=0;i<=N+M;i++)printf("%d ",A[i]*Inv%Mod);
}
Share this Post

Leave a Comment

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*