烷基计数
现在已知碳原子个数 \(n\), 求对应的烷基有多少种同分异构体.
注意: 这里的烷基计数不用考虑空间异构, 能否稳定存在等各种特殊情况. 也就是说, 你要求的是 \(n\) 个点的每个点度数不超过 \(4\) 且根的度数不超过 \(3\) 的有根树的数目.
答案对 \(998244353\) 取模.
题解
记答案的生成函数为 \(F(x)\). 直接 \(F(x)=1+xF(x)^3\) 显然是错的, 因为可能出现同构的情况.
考虑 Burnside 引理, 对 \(3\) 个儿子的置换有 \(6\) 种.
对于 \((1,2,3)?\) 这 \(1?\) 种置换, 每种方案都是不动点.
对于 \((1,3,2),(3,2,1),(2,1,3)\) 这 \(3\) 种置换, 只有在置换中成环的两棵子树相同的方案才是不动点.
对于 \((2,3,1),(3,1,2)\) 这 \(2?\) 种置换, 只有三棵子树都相同的方案才是不动点.
根据 Burnside 引理, 本质不同的方案数是各个置换的不动点数目平均数, 得到
\[ F(x)=1+x\frac{F(x)^3+3F(x^2)F(x)+2F(x^3)}{6} \]
考虑牛顿迭代解出这个方程, 设 \(G(F(x))=x\frac{F(x)^3+3F(x^2)F(x)+2F(x^3)}{6}-F(x)+1\).
若当前已知了 \(F(x)\bmod x^n\), 要求出 \(F(x)\bmod x^{2n}\), 可以发现 \(F(x^2)\bmod x^{2n},F(x^3)\bmod x^{2n}\) 也已知了.
于是可以直接把它们看做常量, 记 \(A(x)=F(x^2)\bmod x^{2n},B(x)=F(x^3)\bmod x^{2n}\).
注意是对 \(F(x)?\) 求导, 所以 \(x?\) 也可以看做常量.
得到 \(G'(F(x))=x\frac{3F(x)^2+3A(x)}{6}-1\), 代入牛顿迭代公式 \(F(x)=F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}\)
\[ F(x)=F_0(x)-\frac{x(F_0(x)^3+3A(x)F_0(x)+2B(x))-6F_0(x)+6}{x(3F_0(x)^2+3A(x))-6} \]
时间复杂度 \(O(n\log n)?\).
- CO int N=262144;
- int omg[2][N],rev[N];
- void NTT(poly&a,int dir){
- int lim=a.size(),len=log2(lim);
- for(int i=0;i<lim;++i) rev[i]=rev[i>>1]>>1|(i&1)<<(len-1);
- for(int i=0;i<lim;++i)if(i<rev[i]) swap(a[i],a[rev[i]]);
- for(int i=1;i<lim;i<<=1)
- for(int j=0;j<lim;j+=i<<1)for(int k=0;k<i;++k){
- int t=mul(omg[dir][N/(i<<1)*k],a[j+i+k]);
- a[j+k+i]=add(a[j+k],mod-t),a[j+k]=add(a[j+k],t);
- }
- if(dir==1){
- int ilim=fpow(lim,mod-2);
- for(int i=0;i<lim;++i) a[i]=mul(a[i],ilim);
- }
- }
- poly operator~(poly a){
- int n=a.size();
- poly b={fpow(a[0],mod-2)};
- if(n==1) return b;
- int lim=2;
- for(;lim<n;lim<<=1){
- poly c(a.begin(),a.begin()+lim);
- c.resize(lim<<1),NTT(c,0);
- b.resize(lim<<1),NTT(b,0);
- for(int i=0;i<lim<<1;++i) b[i]=mul(2+mod-mul(c[i],b[i]),b[i]);
- NTT(b,1),b.resize(lim);
- }
- a.resize(lim<<1),NTT(a,0);
- b.resize(lim<<1),NTT(b,0);
- for(int i=0;i<lim<<1;++i) b[i]=mul(2+mod-mul(a[i],b[i]),b[i]);
- NTT(b,1),b.resize(n);
- return b;
- }
- poly operator*(poly a,poly b){
- int n=a.size()-1,m=b.size()-1;
- int lim=1<<(int)ceil(log2(n+m+1));
- a.resize(lim),NTT(a,0);
- b.resize(lim),NTT(b,0);
- for(int i=0;i<lim;++i) a[i]=mul(a[i],b[i]);
- NTT(a,1),a.resize(n+m+1);
- return a;
- }
- poly solve(int n){
- poly f={1};
- if(n==1) return f;
- for(int lim=2;lim<2*n;lim<<=1){
- f.resize(lim);
- poly a(lim),b(lim);
- for(int i=0;i<lim;i+=2) a[i]=f[i/2];
- for(int i=0;i<lim;i+=3) b[i]=f[i/3];
- poly up=f*f;up.resize(lim);
- for(int i=0;i<lim;++i) up[i]=add(up[i],mul(3,a[i]));
- up=up*f,up.resize(lim);
- for(int i=0;i<lim;++i) up[i]=add(up[i],mul(2,b[i]));
- for(int i=lim-1;i>=1;--i) up[i]=up[i-1];
- up[0]=0;
- for(int i=0;i<lim;++i) up[i]=add(up[i],mod-mul(6,f[i]));
- up[0]=add(up[0],6);
- poly down=f*f;down.resize(lim);
- for(int i=0;i<lim;++i) down[i]=add(mul(3,down[i]),mul(3,a[i]));
- for(int i=lim-1;i>=1;--i) down[i]=down[i-1];
- down[0]=mod-6;
- up=up*~down,up.resize(lim);
- for(int i=0;i<lim;++i) f[i]=add(f[i],mod-up[i]);
- }
- f.resize(n);
- return f;
- }
- int main(){
- omg[0][0]=1,omg[0][1]=fpow(3,(mod-1)/N);
- omg[1][0]=1,omg[1][1]=fpow(omg[0][1],mod-2);
- for(int i=2;i<N;++i){
- omg[0][i]=mul(omg[0][i-1],omg[0][1]);
- omg[1][i]=mul(omg[1][i-1],omg[1][1]);
- }
- int n=read<int>();
- poly f=solve(n+1);
- printf("%d\n",f[n]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3377436.html