拉格朗日反演

如果对于幂级数 $F(x)$和 $G(x)$，有 $G(F(x))=F(G(x))=x$，则称 $F(x)$和 $G(x)$互为复合逆。记 $[x^i]F(x)$为 $F(x)$的 $i$次项系数，以此类推，对于这样的 $F(x)$和 $G(x)$，有：

$$[x^n]G(x)=\frac{1}{n}[x^{n-1}] (\frac{x}{F(x)})^n$$

$$[x^n]H(G(x))=\frac{1}{n}[x^{n-1}]H'(x)(\frac{x}{F(x)})^n$$

解题思路

生成函数 $G(x)$，$[x^i]G(x)=[i \in D]$。

生成函数 $F(x)$，$[x^i]F(x)$为根节点价值为 $i$的多叉树的个数。

则 $F(x)=G(F(x))+x$

那么 $F(x)-G(F(x))=x$

所以 $x-G(x)$和 $F(x)$互为复合逆。

就可以求解了。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int mod=950009857,G=7,N=262150;
int n,m;
int g[N],f[N],rev[N],len[N],inv[N],k1[N],k2[N],k3[N],k4[N],k5[N],k6[N];

int qm(int x) {return x>=mod?x-mod:x;}
int ksm(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
    return re;
}
void getrev(int n)
    {for(RI i=0;i<n;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(len[n]-1));}
void NTT(int *a,int n,int x) {
    for(RI i=0;i<n;++i) if(rev[i]>i) swap(a[i],a[rev[i]]);
    for(RI i=1;i<n;i<<=1) {
        int gn=ksm(G,(mod-1)/(i<<1));
        for(RI j=0;j<n;j+=(i<<1)) {
            int t1,t2,g=1;
            for(RI k=0;k<i;++k,g=1LL*g*gn%mod) {
                t1=a[j+k],t2=1LL*g*a[j+i+k]%mod;
                a[j+k]=qm(t1+t2),a[j+i+k]=qm(t1-t2+mod);
            }
        }
    }
    if(x==1) return;
    reverse(a+1,a+n);for(RI i=0;i<n;++i) a[i]=1LL*a[i]*inv[n]%mod;
}
void getinv(int *a,int *b,int n) {
    if(n==1) {b[0]=ksm(a[0],mod-2),b[1]=0;return;}
    getinv(a,b,n>>1);int kn=n<<1;
    for(RI i=0;i<n;++i) k1[i]=a[i],k1[i+n]=b[i+n]=0;
    getrev(kn),NTT(k1,kn,1),NTT(b,kn,1);
    for(RI i=0;i<kn;++i) b[i]=1LL*(2LL-1LL*b[i]*k1[i]%mod+mod)%mod*b[i]%mod;
    NTT(b,kn,-1);
    for(RI i=n;i<kn;++i) b[i]=0;
}
void getJF(int *a,int *b,int n)
    {for(RI i=1;i<n;++i) b[i]=1LL*a[i-1]*inv[i]%mod; b[0]=0;}
void getdao(int *a,int *b,int n)
    {for(RI i=1;i<n;++i) b[i-1]=1LL*a[i]*i%mod; b[n-1]=0;}
void getln(int *a,int *b,int n) {
    getdao(a,k3,n),getinv(a,k4,n);
    int kn=n<<1;
    for(RI i=n;i<kn;++i) k3[i]=k4[i]=0;
    getrev(kn),NTT(k3,kn,1),NTT(k4,kn,1);
    for(RI i=0;i<kn;++i) k3[i]=1LL*k3[i]*k4[i]%mod;
    NTT(k3,kn,-1),getJF(k3,b,n);
    for(RI i=n;i<kn;++i) b[i]=0;
}
void getexp(int *a,int *b,int n) {
    if(n==1) {b[0]=1,b[1]=0;return;}
    getexp(a,b,n>>1);int kn=n<<1;
    getln(b,k5,n);
    for(RI i=0;i<n;++i) k6[i]=qm(a[i]-k5[i]+mod),k6[i+n]=b[i+n]=0;
    k6[0]=qm(k6[0]+1);
    getrev(kn),NTT(b,kn,1),NTT(k6,kn,1);
    for(RI i=0;i<kn;++i) b[i]=1LL*b[i]*k6[i]%mod;
    NTT(b,kn,-1);
    for(RI i=n;i<kn;++i) b[i]=0;
}
void getksm(int *a,int *b,int n,int K) {
    getln(a,k2,n);
    for(RI i=0;i<n;++i) k2[i]=1LL*k2[i]*K%mod;
    getexp(k2,b,n);
}
void lagrange_inversion(int kn) {
    getinv(g,f,kn);
    for(RI i=0;i<kn;++i) f[kn+i]=g[kn+i]=g[i]=0;
    getksm(f,g,kn,n);
    printf("%lld\n",1LL*g[n-1]*inv[n]%mod);
}

int main()
{
    n=read(),m=read();
    for(RI i=1;i<=m;++i) g[read()-1]=mod-1;
    g[0]=qm(g[0]+1);
    int kn=1;while(kn<=n) kn<<=1,len[kn]=len[kn>>1]+1;
    len[kn<<1]=len[kn]+1,inv[0]=inv[1]=1;
    for(RI i=2;i<=(kn<<1);++i) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
    lagrange_inversion(kn);
    return 0;
}