BZOJ3625 CF438E 小朋友与二叉树

心态崩了不放传送门了辣鸡bz

还是正经一点写一下题解= =

就是显然我们可以把权值写成生成函数形式g(0/1序列)来表示权值是否出现

然后f来表示总的方案数

可以列出 $f = f^2g+1$ 分别枚举左右子树和空树的情况

然后解方程得到 $f = \frac{1 \pm \sqrt{1-4g}}{2g}$

显然开根开出来常数项是1 而g不带常数项那么就必须取-才能保证除法有效

然后为了计算方便我们把柿子写成 $f = \frac{2}{1+\sqrt{1-4g}}$ （平方差上下同乘）

然后就是多项式开根和多项式求逆了

多项式求逆可以戳我的【学习笔记】

然后开根是类似的也是通过倍增可以得到 $B = \frac{A+B'^2}{2B'} (mod\ x^n)$ 递归求解就好了

这个最可怕的是 $T(n/2) +O(nlgn) =O(nlgn)$ 所以是随便套就非常恐怖了（囧

然后我就发现我的写法写多项式开根非常麻烦然后就开始胡乱改

常数上天 BZT飞

本来写的心态就很不好懒得改了= =

所以这份代码BZ是会T掉的小心食用qwq

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define inf 20021225
#define wph 998244353
#define G 3
#define mxn 1600010
#define inv2 499122177
#define int ll
using namespace std;
int rev[mxn],inv;

int ksm(int bs,int mi)
{
 int ans=1;
 while(mi)
 {
  if(mi&1)    ans=(ll)ans*bs%wph;
  bs=(ll)bs*bs%wph; mi>>=1;
 }
 return ans;
}

int init(int n)
{
 int lim=1,l=0;
 while(lim<n)    lim<<=1,l++;
 for(int i=0;i<lim;i++)
  rev[i] = (rev[i>>1]>>1)|((i&1)<<(l-1));
 inv = ksm(lim,wph-2);
 return lim;
}

void ntt(int *a,int n,int f)
{
 for(int i=0;i<n;i++)
        if(rev[i]>i) swap(a[i],a[rev[i]]);
    for(int k=2;k<=n;k<<=1)
    {
        int Wn=ksm(G,(wph-1)/k),mid=k>>1;
        if(f) Wn=ksm(Wn,wph-2);
        for(int w=1,i=0;i<n;i+=k,w=1)
        {
            for(int j=0;j<mid;j++,w=(ll)w*Wn%wph)
            {
                int x=a[i+j],y=(ll)w*a[i+j+mid]%wph;
                a[i+j]=(x+y)%wph;a[i+j+mid]=(x-y+wph)%wph;
            }
        }
    }
    if(f) for(int i=0;i<n;i++) a[i]=(ll)a[i]*inv%wph;
}
int f[mxn],g[mxn],h[mxn];
void poly_inv(int *a,int n)
{
 if(n==1)
 {
  g[0] = ksm(a[0],wph-2);
  return;
 }
 int mid = (n+1)>>1;
 poly_inv(a,mid);
 int lim = init(n<<1);
 for(int i=0;i<n;i++)    h[i]=a[i];
 for(int i=n;i<lim;i++)  h[i]=0;
 ntt(h,lim,0); ntt(g,lim,0);
 for(int i=0;i<lim;i++)
  g[i] = (2ll - (ll)h[i]*g[i]%wph + wph)%wph *g[i] %wph;
 ntt(g,lim,1);
 for(int i=n;i<lim;i++) g[i]=0;
}
int d[mxn],t[mxn];
void poly_sqrt(int a[],int n)
{
 //printf("%d\n",n);
 if(n==1){d[0] = 1;return;}
 int mid = n>>1; poly_sqrt(a,mid);
 int lim = init(n);// while(lim<(n<<1)) lim<<=1;
 memset(g,0ll,sizeof(ll)*n*2);
 poly_inv(d,n);
 for(int i=0;i<n;i++) h[i]=a[i];
 for(int i=n;i<lim*2;i++) h[i]=0;
 lim = init(n<<1);
 ntt(h,lim,0); ntt(g,lim,0); ntt(d,lim,0);
 for(int i=0;i<lim;i++)
  d[i] = ((ll)h[i]*g[i]%wph + d[i])%wph *inv2%wph;
 ntt(d,lim,1);
 for(int i=n;i<lim;i++) d[i]=0;
}
int a[mxn];
signed main()
{
 int n,m,x;
 scanf("%lld%lld",&n,&m);
 for(int i=1;i<=n;i++)
 {
  scanf("%lld",&x);
  if(x<=m) f[x] = wph - 4;
 }
 f[0]=1;
 int lim=init(m<<1);
 poly_sqrt(f,lim);
 d[0]++;
 //for(int i=0;i<(m<<1);i++) printf("%d ",d[i]);
 memset(g,0,sizeof(g));
 lim = init(m<<1);
 poly_inv(d,lim);// printf("%d ",g[0]*2%wph);
 for(int i=1;i<=m;i++) printf("%lld\n",g[i]*2%wph);
 /**scanf("%d",&n);
 for(int i=0;i<n;i++) scanf("%d",&f[i]);
 poly_inv(f,n);
 for(int i=0;i<n;i++) printf("%d ",g[i]);*/
    return 0;
}
/**
*/