如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
烷基计数
求 $n$ 个点的每个点度数不超过 $4$ 且根的度数不超过 $3$ 的无标号有根树的数目。
设答案的 $\text{OGF}$ 为 $A(x)$，考虑根的子节点，使用 $\text {Burside}$ 引理得到：
\[A(x)=x\frac{A(x)^3+3A(x^2)A(x)+2A(x^3)}{6}+1\]考虑牛顿迭代，设 $A_*(x)$ 为 $\bmod x^{\frac{n}{2}}$ 的答案。
\[F(A(x))=x\frac{A(x)^3+3A(x^2)A(x)+2A(x^3)}{6}+1-A(x)=0\\ A(x)=A_*(x)-\frac{F(A_*(x))}{F'(A_*(x))}\pmod{x^n}\\ F'(A(x))=x\frac{A(x)^2+A(x^2)}{2}-1\]烯烃计数
断开碳-碳双键两边是根节点度数不超过 $2$，其他点子节点个数小于等于 $3$ 的无标号有根树。
这棵树的 $\text{OGF}$ 为 $P(x)$：
\[P(x)=x\frac{A(x)^2+A(x^2)}{2}+1\]烯烃的 $\text{OGF}$ 为 $G(x)$：
\[G(x)=x\frac{(P(x)-1)^2+P(x^2)-1}{2}\]#include<cstdio>
#include<algorithm>
int const mod=998244353,g=3,gi=998244354/3,inv2=998244354/2,inv6=998244354/6,maxn=800010;
int pow(int x,int y){
int res=1;
while(y){
if(y&1)res=1ll*x*res%mod;
x=1ll*x*x%mod,y>>=1;
}
return res;
}
struct NTT{
int r[maxn],lim;
NTT():r(),lim(){}
void getr(int const &li){
lim=li;
for(int i=0;i<lim;i++)r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1));
}
void operator ()(int *a,int const &type)const{
for(int i=0;i<lim;i++)if(i<r[i])std::swap(a[i],a[r[i]]);
for(int mid=1;mid<lim;mid<<=1){
int rt=pow(type==1?g:gi,(mod-1)/(mid<<1));
for(int r=mid<<1,j=0;j<lim;j+=r){
int p=1;
for(int k=0;k<mid;k++,p=1ll*p*rt%mod){
int x=a[j+k],y=1ll*p*a[j+k+mid]%mod;
a[j+k]=(x+y)%mod,a[j+mid+k]=(x-y+mod)%mod;
}
}
}
if(type==-1)for(int p=pow(lim,mod-2),i=0;i<lim;i++)a[i]=1ll*a[i]*p%mod;
}
}ntt;
void inv(int const *a,int *ans,int const &m){
static int tmp[maxn];
for(int i=0;i<m<<1;i++)tmp[i]=ans[i]=0;
ans[0]=pow(a[0],mod-2);
for(int n=2,lim;n<=m;n<<=1){
for(int i=0;i<n;i++)tmp[i]=a[i];
ntt.getr(lim=n<<1);
ntt(tmp,1),ntt(ans,1);
for(int i=0;i<lim;i++)ans[i]=ans[i]*(2-1ll*ans[i]*tmp[i]%mod+mod)%mod;
ntt(ans,-1);
for(int i=n;i<lim;i++)ans[i]=0;
}
}
void solve(int *ans,int const &m){
static int a3[maxn],a2[maxn],a1[maxn],fz[maxn],fm[maxn];
ans[0]=1;
for(int n=2,lim;n<=m;n<<=1){
for(int i=0;i<n<<1;i++)a1[i]=a2[i]=a3[i]=fz[i]=fm[i]=0;
for(int i=0;i<n;i++)a1[i]=ans[i];
for(int i=0;i<n;i+=2)a2[i]=ans[i/2];
for(int i=0;i<n;i+=3)a3[i]=ans[i/3];
ntt.getr(lim=n<<2);
ntt(a1,1);
for(int i=0;i<lim;i++)a1[i]=1ll*a1[i]*a1[i]%mod*a1[i]%mod;
ntt(a1,-1);
for(int i=0;i<n;i++)fz[i]=a1[i],a1[i]=ans[i],fm[i]=a2[i];
for(int i=n;i<lim;i++)a1[i]=0;
ntt.getr(lim=n<<1);
ntt(a1,1),ntt(a2,1);
for(int i=0;i<lim;i++)a2[i]=1ll*a2[i]*a1[i]%mod,a1[i]=1ll*a1[i]*a1[i]%mod;
ntt(a1,-1),ntt(a2,-1);
for(int i=n-1;i;i--)fz[i]=(1ll*inv6*fz[i-1]+1ll*inv2*a2[i-1]+1ll*gi*a3[i-1])%mod;
fz[0]=1;
for(int i=0;i<n;i++)fz[i]=(fz[i]-ans[i]+mod)%mod;
for(int i=n-1;i;i--)fm[i]=1ll*inv2*(a1[i-1]+fm[i-1])%mod;
fm[0]=mod-1;
for(int i=n;i<lim;i++)fz[i]=fm[i]=0;
inv(fm,a1,n);
ntt.getr(lim);
ntt(a1,1),ntt(fz,1);
for(int i=0;i<lim;i++)a1[i]=1ll*a1[i]*fz[i]%mod;
ntt(a1,-1);
for(int i=0;i<n;i++)ans[i]=(ans[i]-a1[i]+mod)%mod;
}
}
int a[maxn],b[maxn],lim=1<<17;
int main(){
solve(a,lim);
for(int i=0;i<lim;i++)b[i]=a[i];
for(int i=0;i<lim;i++)a[i]=0;
for(int i=0;i<lim;i+=2)a[i]=b[i>>1];
ntt.getr(lim<<1);
ntt(b,1);
for(int i=0;i<lim<<1;i++)b[i]=1ll*b[i]*b[i]%mod;
ntt(b,-1);
for(int i=lim-1;i;i--)a[i]=1ll*inv2*(a[i-1]+b[i-1])%mod;
a[0]=0;
for(int i=0;i<lim<<1;i++)b[i]=0;
for(int i=0;i<lim;i+=2)b[i]=a[i>>1];
ntt(a,1);
for(int i=0;i<lim<<1;i++)a[i]=1ll*a[i]*a[i]%mod;
ntt(a,-1);
for(int i=lim-1;~i;i--)a[i]=1ll*inv2*(a[i]+b[i])%mod;
int t;
scanf("%d",&t);
for(int i=2;i<=t;i++)printf("%d\n",a[i]);
return 0;
}