必威体育Betway必威体育官网
当前位置:首页 > IT技术

计算烷烃的同分异构体个数

时间:2019-10-29 22:44:37来源:IT技术作者:seo实验室小编阅读:56次「手机版」
 

同分异构体

相当于计算度数不超过4的无标号无根树个数。按照无根树的套路,我们直接枚举子树即可。

但是无根树可以用exp来搞,这个度数有限制。

我们可以换一种方法,显然子树每个点度数不超过3,记其生成函数AAA,可以用Polya定义来计数:

首先假设儿子彼此有序,然后规定如果某个置换之后得到两个等价的东西,那么这两个算一个方案。 我们枚举每一个置换,利用Burnside引理,容易得到:

A=1+x2A(x3)+3A(x2)A(x)+A(x)36A=1+x\frac{2A(x^3)+3A(x^2)A(x)+A(x)^3}{6}A=1+x62A(x3)+3A(x2)A(x)+A(x)3​

相当于每种置换的每个循环节内部必须严格相等。 枚举环然后系数就是这样的置换的个数,利用分治FFT在O(nlog2n)O(n\log^2n)O(nlog2n)时间内预处理。

然后用经典的枚举重心的儿子的方法,就可以在O(nlogn)O(n \log n )O(nlogn)的时间内解决单组询问。

考虑如何解决多组询问,我们发现,对于任意一棵无根树,我们记其点的等价类为ppp个,边的等价类有qqq个,对称边(两边的点等价)有sss个,那么有$s\le 1 ,且,且p-q+s=1$。

证明如下:

如果有对称边,那么显然pq=0pq+s=1p-q=0 \rightarrow p-q+s=1p−q=0→p−q+s=1。

否则等价点不会为重心,重心等价类只有1个点,重心一定在其路径上,他们的父亲是等价边。 我们可以得到pq=1p-q=1p−q=1 (加上重心)。

然后求出p,q,s\sum p , \sum q , \sum s∑p,∑q,∑s即可。

p\sum p∑p相当于有根树计数,是4个儿子拼起来,同理用Polya可得:

P(x)=x6A(x4)+6A(x2)A2(x)+3A2(x2)+8A(x3)A(x)+A(x4)24P(x)=x\frac{6A(x^4)+6A(x^2)A^2(x)+3A^2(x^2)+8A(x^3)A(x)+A(x^4)}{24}P(x)=x246A(x4)+6A(x2)A2(x)+3A2(x2)+8A(x3)A(x)+A(x4)​

q\sum q∑q相当于拼接两棵子树:

Q(x)=(A(x)1)2+(A(x2)1)2Q(x)=\frac{(A(x)-1)^2+(A(x^2)-1)}{2}Q(x)=2(A(x)−1)2+(A(x2)−1)​

s\sum s∑s相当于拼接两棵相同子树:

S(x)=A(x2)S(x)=A(x^2)S(x)=A(x2)

然后就做完了。

不过求AAA时候分治FFT要稍微修改一下,因为A[0,mid]A[0,mid]A[0,mid]对A[mid+1,r]A[mid+1,r]A[mid+1,r]的贡献要用到[mid+1,r][mid+1,r][mid+1,r],这个我们特判一下lll就行了,然后没计算到的贡献在下面分治的时候额外加上即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int RLEN=1<<18|1;
inline char nc() {
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob) ? -1 : *ib++;
}
inline int rd() {
	char ch=nc(); int i=0,f=1;
	while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();}
	while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();}
	return i*f;
}
inline void W(int x) {
	static int buf[50];
	if(!x) {putchar('0'); return;}
	if(x<0) {putchar('-'); x=-x;}
	while(x) {buf[++buf[0]]=x%10; x/=10;}
	while(buf[0]) {putchar(buf[buf[0]--]+'0');}
}

const int mod=998244353, G=3;
inline int add(int x,int y) {return (x+y>=mod) ? (x+y-mod) : (x+y);}
inline int dec(int x,int y) {return (x-y<0) ? (x-y+mod) : (x-y);}
inline int mul(int x,int y) {return (LL)x*y%mod;}
inline int power(int a,int b,int rs=1) {for(;b;b>>=1,a=mul(a,a)) if(b&1) rs=mul(rs,a); return rs;}

const int N=1<<20|1;
const int inv6=power(6,mod-2), inv2=(mod+1)/2, inv24=mul(inv2,mul(inv2,inv6)); 
int n,k,w[N],pos[N],A[N],B[N],tp[N],tp2[N],tp3[N];
inline void init(int nn) {
	for(k=1;k<=nn;k<<=1);
	for(int i=1;i<k;i++) pos[i]=(i&1) ? ((pos[i>>1]>>1)^(k>>1)) : (pos[i>>1]>>1);
}
inline void dft(int *a,int o=1) {
	for(int i=1;i<k;i++) if(pos[i]>i) swap(a[pos[i]],a[i]);
	for(int bl=1;bl<k;bl<<=1) {
		int tl=bl<<1, wn=power(G,(mod-1)/tl);
		w[0]=1; for(int i=1;i<bl;i++) w[i]=mul(w[i-1],wn);
		for(int bg=0;bg<k;bg+=tl)
			for(int j=0;j<bl;j++) {
				int &t1=a[bg+j], &t2=a[bg+j+bl], t=mul(t2,w[j]);
				t2=dec(t1,t); t1=add(t1,t);
			}
	}
	if(!~o) {
		const int inv=power(k,mod-2); reverse(a+1,a+k);
		for(int i=0;i<k;i++) a[i]=mul(a[i],inv);
	}
}
inline void solve(int l,int r) {
	if(l==r) {
		if(!l) A[l]=1;
		else A[l]=add(A[l],((l%3==1) ? mul(2,A[l/3]) : 0)), A[l]=mul(A[l],inv6);
		return;
	} 
	int mid=(l+r)>>1, len=r-l;
	solve(l,mid); init(len*2+mid-l);
	memset(tp,0,sizeof(int)*k); 
	memset(tp2,0,sizeof(int)*k);
	memset(tp3,0,sizeof(int)*k);
	memcpy(tp,A+l,sizeof(int)*(mid-l+1));
	memcpy(tp2,A,sizeof(int)*len);
	for(int i=0,j;(j=i*2)<=len;i++) tp3[j]=A[i];
	
	dft(tp); dft(tp2); dft(tp3);
	for(int i=0;i<k;i++) tp2[i]=mul(tp2[i],mul(tp2[i],tp[i]));
	dft(tp2,-1);
	if(!l) {
		for(int i=mid+1;i<=r;i++) A[i]=add(A[i],tp2[i-l-1]);
	} else {
		for(int i=mid+1;i<=r;i++) A[i]=add(A[i],mul(tp2[i-l-1],3));
	} 
	for(int i=0;i<k;i++) tp[i]=mul(tp[i],tp3[i]);
	dft(tp,-1);
	for(int i=mid+1;i<=r;i++) A[i]=add(A[i],mul(tp[i-l-1],3));
	solve(mid+1,r);
}
const int L=1e5;
int main() {
	solve(0,n=L); init(L*4);
	memset(tp,0,sizeof(int)*k);
	memset(tp2,0,sizeof(int)*k);
	memset(tp3,0,sizeof(int)*k);
	for(int i=0;i<=n;i++) tp[i]=A[i];
	for(int i=0;i*2<=n;i++) tp2[i*2]=A[i];
	for(int i=0;i*3<=n;i++) tp3[i*3]=A[i];
	dft(tp); dft(tp2); dft(tp3);
	for(int i=0;i<k;i++) {
		int s=0;
		s=add(s,power(tp[i],4));
		s=add(s,mul(6,mul(tp2[i],power(tp[i],2))));
		s=add(s,mul(3,power(tp2[i],2)));
		s=add(s,mul(8,mul(tp3[i],tp[i])));
		tp[i]=s;
	} dft(tp,-1);
	for(int i=0;i<=n;i++) 
		B[i]=add(tp[i],(!(i%4)) ? mul(6,A[i/4]) : 0), B[i]=mul(B[i],inv24);
	for(int i=n;i;i--) B[i]=B[i-1]; B[0]=0;
	for(int i=0;i<=n;i+=2) B[i]=add(B[i],A[i/2]);
	memset(tp,0,sizeof(int)*k);
	for(int i=1;i<=n;i++) tp[i]=A[i];
	dft(tp); 
	for(int i=0;i<k;i++) tp[i]=mul(tp[i],tp[i]);
	dft(tp,-1);
	for(int i=1;i<=n;i++) B[i]=dec(B[i],mul(tp[i],inv2));
	for(int i=2;i<=n;i+=2) B[i]=dec(B[i],mul(A[i/2],inv2));
	for(int T=rd();T;T--)
		W(B[rd()]), putchar('\n');
}

文章最后发布于: 2018-07-08 18:31:58

相关阅读

分享到:

栏目导航

推荐阅读

热门阅读