Loading...

多项式快速幂

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

$B(x)\equiv A^m(x)\pmod {x^n}$

则$lnB(x)\equiv mlnA(x)\pmod {x^n}$

拉个板子就好

#include <bits/stdc++.h>
#define maxn 500005
#define int long long
#define cl(a) memset(a,0,sizeof(a))
using namespace std;
const int mod=998244353,ge=3;
int n,l,k,a[maxn],b[maxn],c[maxn],d[maxn],e[maxn],qwq[maxn],qaq[maxn],pap[maxn],lim,r[maxn];
int ksm(int qaq,int f)
{
    int res=1;
    while(f)
    {
        if(f&1) 
        {
            res=res*qaq%mod;
        }
        qaq=qaq*qaq%mod;
        f>>=1;
    }
    return res;
}
void NTT(int *x,int flag)
{
    for(int i=0;i<lim;i++) 
    {
        if(i<r[i]) 
        {
            swap(x[i],x[r[i]]);
        }
    }
    for(int mid=1;mid<lim;mid<<=1)
    {
        int wn=ksm(ge,flag==1?(mod-1)/(mid<<1):(mod-1-(mod-1)/(mid<<1)));
        for(int r=(mid<<1),i=0;i<lim;i+=r)
        {
            int w=1;
            for(int k=0;k<mid;k++,w=w*wn%mod)
            {
                int m1=x[i+k],m2=w*x[i+mid+k]%mod;
                x[i+k]=(m1+m2)%mod,x[i+mid+k]=(m1-m2+mod)%mod;
            }
        }
    }
}
void getinv(int *f,int *g,int len)
{
    if(len==1)
    {
        g[0]=ksm(f[0],mod-2);
        return;
    }
    getinv(f,g,len+1>>1);
    lim=1;
    l=0;
    while(lim<(len<<1))
    {
        lim<<=1;
        l++;
    }
    for(int i=1;i<lim;i++) 
    {
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    }
    for(int i=0;i<len;i++) 
    {
        c[i]=f[i];
    }
    for(int i=len;i<lim;i++) 
    {
        c[i]=0;
    }
    NTT(c,1),NTT(g,1);
    for(int i=0;i<lim;i++) 
    {
        g[i]=((2ll-g[i]*c[i]%mod)+mod)%mod*g[i]%mod;
    }
    NTT(g,-1);
    int ny=ksm(lim,mod-2);
    for(int i=0;i<len;i++)
    {
        g[i]=g[i]*ny%mod;
    }
    for(int i=len;i<lim;i++) 
    {
        g[i]=0;
    }
}
void dao(int *f,int *g,int len)
{
    for(int i=1;i<len;i++) 
    {
        g[i-1]=i*f[i]%mod;
    }
    g[len-1]=0;
}
void gint(int *f,int *g,int len)
{
    for(int i=1;i<len;i++) 
    {
        g[i]=f[i-1]*ksm(i,mod-2)%mod;
    }
    g[0]=0;
}
void getln(int *f,int *g,int len)
{
    dao(f,b,len),getinv(f,a,len);
    lim=1,l=0;
    while(lim<(len<<1))
    {
        lim<<=1;
        l++;
    }
    for(int i=1;i<lim;i++) 
    {
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    }
    NTT(a,1),NTT(b,1);
    for(int i=0;i<lim;i++) 
    {
        b[i]=a[i]*b[i]%mod;
    }
    NTT(b,-1);
    int ny=ksm(lim,mod-2);
    for(int i=0;i<len;i++)
    {
        b[i]=b[i]*ny%mod;
    }
    gint(b,g,len);
    memset(a,0,sizeof(a));
    for(int i=len;i<lim;i++) 
    {
        g[i]=0;
    }
}
void getexp(int *f,int *g,int len)
{
    if(len==1)
    {
        g[0]=1;
        return;
    }
    getexp(f,g,len+1>>1);
    lim=1,l=0;
    while(lim<(len<<1))
    {
        lim<<=1;
        l++;
    }
    for(int i=1;i<lim;i++) 
    {
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    }
    for(int i=0;i<(len<<1);i++) 
    {
        d[i]=e[i]=0;
    }
    getln(g,d,len);
    for(int i=0;i<len;i++) 
    {
        e[i]=f[i];
    }
    NTT(g,1),NTT(d,1),NTT(e,1);
    for(int i=0;i<lim;i++) 
    {
        g[i]=(1ll-d[i]+e[i]+mod)*g[i]%mod;
    }
    NTT(g,-1);
    int ny=ksm(lim,mod-2);
    for(int i=0;i<len;i++)
    {
        g[i]=g[i]*ny%mod;
    }
    for(int i=len;i<lim;i++) 
    {
        g[i]=0;
    }
}
void getsqrt(int *f,int *g)
{
    getln(f,pap,n);
    cl(b);
    int ny=ksm(2,mod-2);
    for(int i=0;i<n;i++)
    {
        pap[i]=pap[i]*ny%mod;
    }
    getexp(pap,g,n);
    cl(b),cl(pap);
}
int read()
{
    int x=0;
    char ch=getchar();
    while(!isdigit(ch))
    {
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=((x<<3)+(x<<1)+ch-48)%mod;
        ch=getchar();
    }
    return x;
}
signed main()
{
    scanf("%lld",&n);
    k=read();
    for(int i=0;i<n;i++) 
    {
        scanf("%lld",&qwq[i]);
    }
    getln(qwq,qaq,n);
    for(int i=0;i<n;i++) 
    {
        qaq[i]=qaq[i]*k%mod;
    }
    cl(b);
    getexp(qaq,pap,n);
    for(int i=0;i<n;i++)
    {
        printf("%lld ",pap[i]);
    }
    return 0;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名