题目概述

求用集合 $S$ 中的点权构造点权和为 $[1,m]$ 的二叉树的方案数。

解题报告

生成函数什么的好大啊，我好菜啊。令 $C(x)$ 表示所有点权的生成函数，我想的是：

$$ F(x)=\sum_{i=0}^{+\infty}H_iC^i(x) $$

其中 $H_i​$ 表示卡特兰数第 $i​$ 项，然后会发现这个东西不可算，于是就凉了。

实际上我们可以像卡特兰数那样递推： $f_0=1,f_i=\sum_{t=1}^{n}\sum_{j=0}^{i-c_t}f_jf_{i-j-c_t}$ ，改成生成函数就是：

$$ F(x)=F^2(x)C(x)+1 $$

其中那个 $1$ 就是 $f_0$ ，我们使用一元二次方程求根公式：

$$ F(x)={1\pm\sqrt{1-4C(x)}\over 2C(x)} $$

考虑到 $f_0=1$ ，所以当 $x\to 0$ 时应该有 $C(x)=0,F(x)=1$ ，所以应该是：

$$ F(x)={1-\sqrt{1-4C(x)}\over 2C(x)}={2\over 1+\sqrt{1-4C(x)}} $$

就可以多项式开根和多项式求逆做啦。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1<<18,MOD=998244353,INV2=MOD+1>>1;

int n,m,c[maxn+5],a[maxn+5],rev[maxn+5],pw[2][maxn+5],tem[maxn+5],inv[maxn+5];

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void Pre(int n){
    for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
    for (int i=2;i<=n;i<<=1) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2);
}
inline void NTT(int *a,int n,int f){
    for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int k=1;k<n;k<<=1){
        int gn=pw[f<0][k<<1],g=1,x,y;
        for (int i=0;i<n;i+=k<<1,g=1)
            for (int j=0;j<k;j++,g=(LL)g*gn%MOD)
                x=a[i+j],y=(LL)a[i+j+k]*g%MOD,AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);
    }if (f<0) for (int i=0,INV=Pow(n,MOD-2);i<n;i++) a[i]=(LL)a[i]*INV%MOD;
}
void Inv(int *a,int *b,int n){
    if (n==1) {b[0]=Pow(a[0],MOD-2);return;}Inv(a,b,n>>1);Pre(n<<1);
    for (int i=0;i<n;i++) tem[i]=a[i],tem[i+n]=b[i+n]=0;NTT(tem,n<<1,1);NTT(b,n<<1,1);
    for (int i=0;i<(n<<1);i++) tem[i]=(LL)b[i]*(2+MOD-(LL)tem[i]*b[i]%MOD)%MOD;
    NTT(tem,n<<1,-1);for (int i=0;i<n;i++) b[i]=tem[i],b[i+n]=0;
}
void Sqrt(int *a,int *b,int n){
    if (n==1) {b[0]=1;return;}Sqrt(a,b,n>>1);Inv(b,inv,n);Pre(n<<1);
    for (int i=0;i<n;i++) tem[i]=a[i],tem[i+n]=0;NTT(tem,n<<1,1);NTT(inv,n<<1,1);
    for (int i=0;i<(n<<1);i++) tem[i]=(LL)tem[i]*inv[i]%MOD;
    NTT(tem,n<<1,-1);for (int i=0;i<n;i++) b[i]=(LL)(b[i]+tem[i])*INV2%MOD;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);c[0]=1;for (int i=1,x;i<=n;i++) scanf("%d",&x),AMOD(c[x],MOD-4);
    int t;for (t=1;t<=m;t<<=1);Sqrt(c,a,t);AMOD(a[0],1);Inv(a,c,t);
    for (int i=1;i<=m;i++) printf("%d\n",(c[i]<<1)%MOD);return 0;
}