[bzoj3625] 小朋友和二叉树
生成函数不难推出，给定的A，然后求F=F*F*A+1
然后要注意的是这里直接套公式然后求的话会在求逆的时候崩掉，然后具体处理方法就是把上面的除下来就行了。
最后的式子是:
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
typedef long long ll;
const int mod=998244353,g=3;
int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
int sub(int a,int b){a-=b;return a<0?a+mod:a;}
int mul(int a,int b){return (ll)a*b%mod;}
int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
/*math*/
namespace Template_Poly{
typedef vector<int> Poly;
int rev[N];
Poly Poly_add(Poly A,Poly B){
A.resize(max(A.size(),B.size()));
for(size_t i=0;i<B.size();i++)A[i]=add(A[i],B[i]);
return A;
}
Poly Poly_sub(Poly A,Poly B){
A.resize(max(A.size(),B.size()));
for(size_t i=0;i<B.size();i++)A[i]=sub(A[i],B[i]);
return A;
}
void DFT(int *t,int n,int type){
int l=0;while(1<<l<n)++l;
for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
for(int i=0;i<n;i++)if(rev[i]>i)swap(t[rev[i]],t[i]);
for(int step=1;step<n;step<<=1){
int wn=qpow(g,(mod-1)/(step<<1));
for(int i=0;i<n;i+=step<<1){
int w=1;
for(int k=0;k<step;k++,w=mul(w,wn)){
int x=t[i+k],y=mul(t[i+k+step],w);
t[i+k]=add(x,y),t[i+k+step]=sub(x,y);
}
}
}
if(type==1)return;
for(int i=1;i<n-i;i++)swap(t[i],t[n-i]);
int inv=qpow(n,mod-2);
for(int i=0;i<n;i++)t[i]=mul(t[i],inv);
}
Poly NTT(Poly A,int n,Poly B,int m){
static Poly res,PolA,PolB;
PolA=A,PolB=B;
int len=1;while(len < n+m)len<<=1;
res.resize(len);
PolA.resize(len),PolB.resize(len);
DFT(&PolA[0],len,1);DFT(&PolB[0],len,1);
for(int i=0;i<len;i++) res[i]= mul(PolA[i],PolB[i]);
DFT(&res[0],len,-1);
res.resize(n+m-1);
return res;
}
Poly NTT(Poly A,Poly B){
return NTT(A,A.size(),B,B.size());
}
Poly Poly_inv(Poly A,int n){
if(n==1)return Poly(1,qpow(A[0],mod-2));
int len=1<<((int)ceil(log2(n))+1);
Poly x=Poly_inv(A,(n+1)>>1),y;
x.resize(len),y.resize(len);
for(int i=0;i<n;i++)y[i]=A[i];
DFT(&x[0],len,1),DFT(&y[0],len,1);
for(int i=0;i<len;i++)x[i]=mul(x[i],sub(2,mul(x[i],y[i])));
DFT(&x[0],len,-1);
x.resize(n);
return x;
}
Poly Poly_inv(Poly A){
return Poly_inv(A,A.size());
}
Poly Deri(Poly A){
int n=A.size();
for(int i=1;i<n;i++)A[i-1]=mul(A[i],i);
A.resize(n-1);
return A;
}
Poly Inte(Poly A){
int n=A.size();
A.resize(n+1);
for(int i=n;i;i--)A[i]=mul(A[i-1],qpow(i,mod-2));
A[0]=0;
return A;
}
Poly ln(Poly A){
int len=A.size();
A=Inte(NTT(Deri(A),Poly_inv(A)));
A.resize(len);
return A;
}
Poly exp(Poly A,int n){
if(n==1)return Poly(1,1);
Poly x=exp(A,(n+1)>>1),y;
x.resize(n);
y=ln(x);
for(int i=0;i<n;i++)y[i]=sub(A[i],y[i]);
y[0]++;
x=NTT(x,y);
x.resize(n);
return x;
}
Poly exp(Poly A){
return exp(A,A.size());
}
Poly sqrt(Poly A,int n){
if(n==1)return Poly(1,1);
Poly x=sqrt(A,(n+1)>>1),y;
x.resize(n),y.resize(n);
for(int i=0;i<n;i++)y[i]=A[i];
x=Poly_add(NTT(Poly_inv(x),y),x);
int inv2=qpow(2,mod-2);
for(int i=0;i<n;i++)
x[i]=mul(x[i],inv2);
x.resize(n);
return x;
}
Poly sqrt(Poly A){
return sqrt(A,A.size());
}
}
using namespace Template_Poly;
int n,m;
int a[N];
Poly T,A,B,M;
int main()
{
scanf("%d%d",&n,&m);
T.resize(m+1);A.resize(m+1);
for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]<=m)A[a[i]]++;}
for(int i=0;i<=m;i++)T[i]=mul(4,sub(0,A[i]));
T[0]=add(T[0],1);
T=sqrt(T);
T[0]=add(T[0],1);
T=Poly_inv(T);
for(int i=1;i<=m;i++)printf("%d\n",mul(T[i],2));
}
|
转播
