清真多项式题
题意
每个点的权值可以在集合$ S$中任取
求点权和恰好为$[1..n]$的不同的二叉树数量
数据范围全是$ 10^5$
$ Solution $
设集合$ S$的生成函数为$ C$
考虑暴力$ DP$,枚举当前根节点的权值以及左右子树的权值
有
$f[0]=1$
$ f[x]=\sum\limits_{i=0}^x \sum\limits_{j=0}^{x-i}f[i]f[j]·[C[x-i-j]=1]$
化成生成函数形式即为
$ f=C·f^2+1$
其中$+1$是因为$ C$中不含常数项而多项式$ f$中含有值为$ 1$的常数项
二次方程求解得
$f=\frac{1 \pm \sqrt{1-4C}}{2C}$
因为分母没有常数项，分子显然也不应有常数项
即
$f=\frac{1 - \sqrt{1-4C}}{2C}$
分母没有常数项不能求逆，则分子分母同乘$ 1+ \sqrt{1-4c}$得
$ f=\frac{2}{1+\sqrt{1-4C}}$
直接上多项式开根，求逆的板子即可
时间复杂度$ O(n \ log \ n)$
$ my \ code $
这是一份自带巨大常数的板子
单$ log 10w$需要跑$ 1s+$
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define rt register int
#define ll long long
using namespace std;
namespace fast_IO{
const int IN_LEN=,OUT_LEN=;
char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-;
inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}
inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,,oh-obuf,stdout),oh=obuf;*oh++=x;}
inline void flush(){fwrite(obuf,,oh-obuf,stdout);}
}
using namespace fast_IO;
//#define getchar() getchar_()
//#define putchar(x) putchar_((x))
inline ll read(){
ll x=;char zf=;char ch=getchar();
while(ch!='-'&&!isdigit(ch))ch=getchar();
if(ch=='-')zf=-,ch=getchar();
while(isdigit(ch))x=x*+ch-'',ch=getchar();return x*zf;
}
void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}
void writeln(const ll y){write(y);putchar('\n');}
int k,m,n,x,y,z,cnt,ans; namespace poly{
#define p 998244353
vector<int>R;
vector<int>get(int n){
vector<int>ret(n);
for(rt i=;i<n;i++)ret[i]=read();
return ret;
}
void print(const vector<int>A){for(rt i=;i<A.size();i++)write((A[i]+p)%p),putchar(' ');}
int ksm(int x,int y=p-){
int ans=;
for(rt i=y;i;i>>=,x=1ll*x*x%p)if(i&)ans=1ll*ans*x%p;
return ans;
}
void NTT(int n,vector<int>&A,int fla){
A.resize(n);
for(rt i=;i<n;i++)if(i>R[i])swap(A[i],A[R[i]]);
for(rt i=;i<n;i<<=){
int w=ksm(,(p-)//i);
for(rt j=;j<n;j+=i<<){
int K=;
for(rt k=;k<i;k++,K=1ll*K*w%p){
int x=A[j+k],y=1ll*K*A[i+j+k]%p;
A[j+k]=(x+y)%p,A[i+j+k]=(x-y)%p;
}
}
}
if(fla==-){
reverse(A.begin()+,A.end());
int invn=ksm(n);
for(rt i=;i<n;i++)A[i]=1ll*A[i]*invn%p;
}
}
vector<int>Resize(int n,vector<int>A){A.resize(n);return A;}
vector<int>Mul(vector<int>x,vector<int>y){
int lim=,sz=x.size()+y.size()-;
while(lim<=sz)lim<<=;R.resize(lim);
for(rt i=;i<lim;i++)R[i]=(R[i>>]>>)|(i&)*(lim>>);
NTT(lim,x,);NTT(lim,y,);
for(rt i=;i<lim;i++)x[i]=1ll*x[i]*y[i]%p;
NTT(lim,x,-);x.resize(sz);
return x;
}
vector<int>Inv(vector<int>A,int n=-){
if(n==-)n=A.size();
if(n==)return vector<int>(,ksm(A[]));
vector<int>b=Inv(A,(n+)/);
int lim=;while(lim<=n+n)lim<<=;R.resize(lim);
for(rt i=;i<lim;i++)R[i]=(R[i>>]>>)|(i&)*(lim>>);
A.resize(n);NTT(lim,A,);NTT(lim,b,);
for(rt i=;i<lim;i++)A[i]=1ll*b[i]*(2ll-1ll*A[i]*b[i]%p)%p;
NTT(lim,A,-);A.resize(n);
return A;
}
vector<int>Div(vector<int>A,vector<int>B){
int n=A.size(),m=B.size();
reverse(A.begin(),A.end());
reverse(B.begin(),B.end());
A.resize(n-m+),B.resize(n-m+);
int lim=;while(lim<=*(n-m+))lim<<=;R.resize(lim);
for(rt i=;i<lim;i++)R[i]=(R[i>>]>>)|(i&)*(lim>>);
vector<int>ans=Resize(n-m+,Mul(A,Inv(B)));
reverse(ans.begin(),ans.end());
return ans;
}
vector<int>Add(vector<int>A,vector<int>B){
int len=max(A.size(),B.size());A.resize(len);
for(rt i=;i<len;i++)(A[i]+=B[i])%=p;
return A;
}
vector<int>Sub(vector<int>A,vector<int>B){
int len=max(A.size(),B.size());A.resize(len);
for(rt i=;i<len;i++)(A[i]-=B[i])%=p;
return A;
}
vector<int>Mul(int x,vector<int>A){
for(rt i=;i<A.size();i++)A[i]=1ll*A[i]*x%p;
return A;
}
vector<int>deriv(vector<int>A){//求导
for(rt i=;i<A.size();i++)(A[i-]=1ll*A[i]*i%p);
A.pop_back();return A;
}
vector<int>integ(vector<int>A){//积分
A.push_back();
for(rt i=A.size()-;i>=;i--)A[i+]=1ll*A[i]*ksm(i+)%p;
A[]=;return A;
}
vector<int>Ln(const vector<int>A){return integ(Resize(A.size()-,Mul(deriv(A),Inv(A))));}
vector<int>Exp(vector<int>A,int n=-){
if(n==-)n=A.size();
if(n==)return vector<int>(,);
vector<int>A0=Resize(n,Exp(A,(n+)>>));
vector<int>now=Resize(n,Ln(A0));
for(rt i=;i<n;i++)now[i]=(A[i]-now[i])%p;now[]++;
return Resize(n,Mul(A0,now));
}
struct cp{
ll a,b,z;//a+bsqrt(z)
cp operator *(const cp s)const{
return {(1ll*a*s.a%p+1ll*b*s.b%p*z%p)%p,(1ll*a*s.b%p+1ll*b*s.a)%p,z};
}
};
cp ksm(cp x,int y){
cp ans={,,x.z};
for(rt i=y;i;i>>=,x=x*x)if(i&){
ans=x*ans;
}
return ans;
}
int Sqrt(int n){//求二次剩馀
if(ksm(n,(p-)/)!=)return -;
while(){
x=rand()%p;
if(ksm((1ll*x*x%p-n%p+p)%p,(p-)/)==)continue;
cp ret=ksm({x,,(1ll*x*x%p+p-n)%p},(p+)/);
return min(ret.a,p-ret.a);
}
}
vector<int>GetSqrt(vector<int>A,int n=-){
if(n==-)n=A.size();
if(n==)return vector<int>(,Sqrt(A[]));
vector<int>ans=Resize(n,GetSqrt(A,n+>>)),C(A.begin(),A.begin()+n);
return Resize(n,Mul(ksm(),Add(ans,Mul(Inv(ans),C))));
}
vector<int>Pow(vector<int>A,int k){
A[]=;
return Exp(Mul(k,Ln(A)));
}
//#undef p
};
using namespace poly;
int inv[],v[];
int main(){
m=read();n=read();
vector<int>c(n+);
for(rt i=;i<=m;i++){
x=read();
if(x<=n)c[x]++;
}
vector<int>ans=Mul(-,c);ans[]++;
ans=GetSqrt(ans);ans[]++;
ans=Mul(,Inv(ans));
for(rt i=;i<=n;i++)writeln((ans[i]+p)%p);
return flush(),;
}