题目大意：给定一个集合 S ，对于 i=1...m 求有多少二叉树满足每个节点的权值都在集合 S 中且权值和为 i
构造答案多项式 F(x) 和集合 S 的生成函数 C(x) ，那么
根节点的左子树是一棵二叉树，右子树是一棵二叉树，本身的权值必须在集合S中，此外还有空树的情况
故有 F(x)=F2(x)C(x)+1
解得 F(x)=1±1?4C(x)√2C(x)=21±1?4C(x)√
若等式下方取减号则分母不可逆，舍去
得到 F(x)=21+1?4C(x)√
有关多项式求逆和多项式开根的内容参见Picks的博客
CF上每个点7s时限能过 BZ上我实在没心情卡常数了
[捂脸熊]我整个人都快速傅里叶变换了

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define M 525000 #define P 998244353 #define G 3 #define INV2 499122177 using namespace std; int n,m,l; int a[M],b[M]; long long Quick_Power(long long x,long long y) { long long re=1; while(y) { if(y&1) (re*=x)%=P; (x*=x)%=P; y>>=1; } return re; } void FFT(int a[],int n,int type) { static int temp[M]; int i; if(n==1) return ; for(i=0;i
       
        >1]=a[i],temp[i+n>>1]=a[i+1]; memcpy(a,temp,sizeof(a[0])*n); int *l=a,*r=a+(n>>1); FFT(l,n>>1,type); FFT(r,n>>1,type); long long w=Quick_Power(G,(long long)(P-1)/n*type%(P-1)),wn=1; for(i=0;i
        
         >1;i++,(wn*=w)%=P) temp[i]=(l[i]+wn*r[i])%P,temp[i+(n>>1)]=(l[i]-wn*r[i]%P+P)%P; memcpy(a,temp,sizeof(a[0])*n); } void Get_Inv(int a[],int b[],int n) { static int temp[M]; int i; if(n==1) { b[0]=Quick_Power(a[0],P-2); return ; } Get_Inv(a,b,n>>1); memcpy(temp,a,sizeof(a[0])*n); memset(temp+n,0,sizeof(a[0])*n); FFT(temp,n<<1,1); FFT(b,n<<1,1); for(i=0;i
         
          >1); memset(b_inv,0,sizeof(a[0])*n); Get_Inv(b,b_inv,n); memcpy(temp,a,sizeof(a[0])*n); memset(temp+n,0,sizeof(a[0])*n); FFT(temp,n<<1,1); FFT(b,n<<1,1); FFT(b_inv,n<<1,1); for(i=0;i
          
           >n>>m; for(l=1;l<=m;l<<=1); for(i=1;i<=n;i++) { scanf("%d",&x); if(x<=m) a[x]-=4; if(a[x]<0) a[x]+=P; } a[0]=1; Get_Root(a,b,l); static int c[M],d[M]; memcpy(c,b,sizeof(a[0])*l); (++c[0])%=P; Get_Inv(c,d,l); for(i=1;i<=m;i++) printf("%d\n",(d[i]<<1)%P); return 0; }