P6597 烯烃计数

04 Feb 2021 3526字 12分次数学, 多项式, 生成函数, and Burnside引理
如果这篇博客帮助到你，可以请我喝一杯咖啡~
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;
}

P6597 烯烃计数 gxy001

烷基计数

烯烃计数