bzoj 3625(NTT+多項式求逆+多項式開根)

この問題は私がNTTを探して探したもので、その時「多項式開根」というタイトルを見て、L-leaderのブログを見つけて、べき乗級数のものを補って、2つの数学の授業でマスターしました.
問題面
私はまた問題解を見て、どのように処方して、逆を求めて、それからまた何日も引きずったようです.やっと昨夜眠れなくて、ふと思いついた...
まず生成関数について説明します.簡単に言えば、多項式関数(べき乗級数)を生成できる配列a[0..n]である.
f(x)=∑i=0na[i]∗xi
題意はあなたに二叉樹の各ノードの可能な点権集合Cをあげることで、要素はすべて<=1 e 5で、すべての1<=s<=mに対して、異なる二叉樹が点権とsを満たして、答えは1つのフェルマス数を模します.
g[i]を01配列とし,iがCに現れるか否かを示し,f[i]を重み値とiのシナリオ数とし,すなわち答えである.Fはfの生成関数であり、Gはgの生成関数であり、題意g[0]=0に基づいて空の木が存在するため、f[0]=1である.
私たちは二叉木の根の重み値を列挙することができて、左右の息子を残して子の問題にして、あります
f[x]=∑i=0xg[i]∑j=0x−if[j]∗f[x−i−j]
だいたいわかる
F=F2G .
f[0]=1,g[1]=0により
F=F2G+1
一元二次方程式を解くことにより,f[0]=1,g[1]=0を再結合する
F=21+1−4G−−−−−−√
そして多項式求逆と多項式開根です.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define mmst(a, b) memset(a, b, sizeof(a))
#define mmcp(a, b) memcpy(a, b, sizeof(b))

typedef long long LL;

const int p=998244353,I2=499122177;
const int N=800400;

int cheng(int a,int b)
{
    int res=1;
    for(;b;b>>=1,a=(LL)a*a%p)
    if(b&1)
    res=(LL)res*a%p;
    return res;
}

int n,rev[N];

void init(int lim)
{
    n=1;
    int k=-1;
    while(n1,k++;
    for(int i=0;i>1] >> 1) | ((i&1)<int *a,int ops)
{
    for(int i=0;iif(ifor(int l=2;l<=n;l<<=1)
    {
        int m=l>>1,wn;
        if(ops)
        wn=cheng(3,(p-1)/l);
        else
        wn=cheng(3,p-1-(p-1)/l);
        for(int i=0;iint w=1;
            for(int k=0;k<m;k++)
            {
                int t=(LL)a[i+k+m]*w%p;
                a[i+k+m]=(a[i+k]-t+p)%p;
                a[i+k]=(a[i+k]+t)%p;
                w=(LL)w*wn%p;
            }
        } 
    }
    if(!ops)
    {
        int Inv=cheng(n,p-2);
        for(int i=0;i*Inv%p;
    }
}

int g[N];
int mx=1,by,nn,mm;
int X[N],Y[N],sqr[N],A[N],B[N],C[N];

void Inverse(int *a,int *b,LL len)
{
    if(len==1)
    {
        b[0]=cheng(a[0],p-2);
        return;
    }
    Inverse(a,b,len>>1);
    init(2*len);
    for(int i=0;ifor(int i=0;i>1);i++)
    Y[i]=b[i];

    ntt(X,1);
    ntt(Y,1);
    for(int i=0;i2ll*Y[i]%p-(LL)X[i]*Y[i]%p*Y[i]%p+p)%p;
    ntt(X,0);
    for(int i=0;iif(i>=len)
        b[i]=0;
        else
        b[i]=X[i];
        X[i]=Y[i]=0;
    }
}

void Sqrt(int len)
{
    if(len==1)
    {
        sqr[0]=1;//             1 
        return;
    }
    Sqrt(len>>1);
    Inverse(sqr,A,len);

    for(int i=0;i>1);i++)
    B[i]=sqr[i];
    for(int i=0;i*2);
    ntt(A,1);
    ntt(B,1);
    ntt(C,1);
    for(int i=0;i1ll*C[i]+(LL)B[i]*B[i])%p*I2%p*A[i]%p;
    ntt(A,0);
    for(int i=0;isqr[i]=A[i];
        if(i>=len)
        sqr[i]=0;
        A[i]=B[i]=C[i]=0;
    }
}

int main()
{
    cin>>nn>>mm;
    while(mx<=mm)
    mx<<=1;

    for(int i=1;i<=nn;i++)
    {
        scanf("%d",&by);
        if(by<=mm)
        g[by]=1;
    }

    for(int i=0;iif(g[i])
    g[i]=p-4;
    g[0]=1;

    Sqrt(mx);
    sqr[0]=(sqr[0]+1)%p;

    mmst(g,0);

    Inverse(sqr,g,mx);
    for(int i=1;i<=mm;i++)
    printf("%d
",(g[i]+g[i])%p);

    return 0;
}