The Child and Binary Tree

我们的小朋友很喜欢计算机科学，而且尤其喜欢二叉树。 考虑一个含有(n)个互异正整数的序列(c_1,c_2,dots,c_n)。如果一棵带点权的有根二叉树满足其所有顶点的权值都在集合({c_1,c_n})中，我们的小朋友就会将其称作神犇的。并且他认为，一棵带点权的树的权值，是其所有顶点权值的总和。 给出一个整数(m)，你能对于任意的(s(1 le s le m))计算出权值为(s)的神犇二叉树的个数吗？请参照样例以更好地理解什么样的两棵二叉树会被视为不同的。 我们只需要知道答案关于(998244353)取模后的值。

(1le n le 10^5,1 le m le 10^5)

dreagonm的题解

设答案的生成函数(F)，(F_x)项系数为权值和为(x)的答案。

题目中要求权值必须在集合中出现，这个不好处理，考虑再设一个(C)，(C)的第(x)项如果是(1)代表(x)出现在值域里，如果是(0)，代表(x)没有出现在值域里，然后由于二叉树可以分别对左右子树处理，所以
$$
F_k=sum_{i=1}^k C_i sum_{j=0}^{k-i}F_j F_{k-i-j}

F_0=1
$$

可以看出这是一个卷积的形式
[ F=1+Ctimes Ftimes F ]
然后解一个一元二次方程
[ F=frac{1 pm sqrt{1-4C}}{2C}=frac{2}{1 pm sqrt{1-4C}} ]
因为(C_0=0)，(F_0=1)，所以去掉负号

然后上多项式求逆和多项式开方即可。时间复杂度(O(m log m))。

#include<bits/stdc++.h>
#define co const
#define il inline
template<class T> T read(){
    T x=0,w=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-') w=-w;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*w;
}
template<class T>il T read(T&x){
    return x=read<T>();
}
using namespace std;
typedef long long LL;

co int mod=998244353,g[2]={3,332748118};
il int add(int a,int b){
    return (a+=b)>=mod?a-mod:a;
}
il int mul(int a,int b){
    return (LL)a*b%mod;
}
il int fpow(int a,int b){
    int ans=1;
    for(;b;b>>=1,a=mul(a,a))
        if(b&1) ans=mul(ans,a);
    return ans;
}

typedef vector<int> polynomial;
void num_trans(polynomial&a,int dir){
    int lim=a.size();
    static vector<int> rev,w[2];
    if(rev.size()!=lim){
        rev.resize(lim);
        int len=log2(lim);
        for(int i=0;i<lim;++i) rev[i]=rev[i>>1]>>1|(i&1)<<(len-1);
        for(int dir=0;dir<2;++dir){
            w[dir].resize(lim);
            w[dir][0]=1,w[dir][1]=fpow(g[dir],(mod-1)/lim);
            for(int i=2;i<lim;++i) w[dir][i]=mul(w[dir][i-1],w[dir][1]);
        }
    }
    for(int i=0;i<lim;++i)if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int step=1;step<lim;step<<=1){
        int quot=lim/(step<<1);
        for(int i=0;i<lim;i+=step<<1){
            int j=i+step;
            for(int k=0;k<step;++k){
                int t=mul(w[dir][quot*k],a[j+k]);
                a[j+k]=add(a[i+k],mod-t),a[i+k]=add(a[i+k],t);
            }
        }
    }
    if(dir){
        int ilim=fpow(lim,mod-2);
        for(int i=0;i<lim;++i) a[i]=mul(a[i],ilim);
    }
}
polynomial poly_inv(polynomial a,int n){
    polynomial b(1,fpow(a[0],mod-2));
    if(n==1) return b;
    int lim=2;
    for(;lim<n;lim<<=1){
        polynomial a1(a.begin(),a.begin()+lim);
        a1.resize(lim<<1),num_trans(a1,0);
        b.resize(lim<<1),num_trans(b,0);
        for(int i=0;i<lim<<1;++i) b[i]=mul(add(2,mod-mul(a1[i],b[i])),b[i]);
        num_trans(b,1),b.resize(lim);
    }
    a.resize(lim<<1),num_trans(a,0);
    b.resize(lim<<1),0);
    for(int i=0;i<lim<<1;++i) b[i]=mul(add(2,mod-mul(a[i],b[i]);
    num_trans(b,b.resize(n);
    return b;
}
co int i2=499122177;
polynomial poly_sqrt(polynomial a,1);
    if(n==1) return b;
    int lim=2;
    for(;lim<n;lim<<=1){
        polynomial a1(a.begin(),0);
        b.resize(lim);polynomial b1=poly_inv(b,lim);
        b1.resize(lim<<1),num_trans(b1,0);
        for(int i=0;i<lim<<1;++i) b[i]=mul(add(mul(b[i],b[i]),a1[i]),mul(i2,b1[i]));
        num_trans(b,0);
    b.resize(lim);polynomial b1=poly_inv(b,lim);
    b1.resize(lim<<1),0);
    for(int i=0;i<lim<<1;++i) b[i]=mul(add(mul(b[i],a[i]),b1[i]));
    num_trans(b,b.resize(n);
    return b;
}
int main(){
    int n=read<int>(),m=read<int>();
    polynomial c(m+1);
    for(int i=1;i<=n;++i){
        int w=read<int>();
        if(w<=m) c[w]=1;
    }
    for(int i=0;i<=m;++i) c[i]=mul(mod-4,c[i]);
    c[0]=add(c[0],1);
    c=poly_sqrt(c,m+1);
    c[0]=add(c[0],1);
    c=poly_inv(c,m+1);
    for(int i=1;i<=m;++i) printf("%dn",mul(2,c[i]));
    return 0;
}