题意

求$n$个碳原子的烷基的同分异构体数目。

简单版

$n\le 500$
要求的是每个点的度数不大于$4$且根节点的度数不大于$3$的无标号有根树数量。
设$f_i$表示有$i$个碳原子的烷基数目，枚举两个子树的大小算贡献即可。
时间复杂度$O(n^3)$

加强版

$n\le 5000$
设$f_{k,i,j}$表示有$i$个碳原子，且根的度数为$j$且最大子树大小不超过$k$的烷基数量。
转移的时候枚举当前的树有多少棵大小为$k$的子树。
不难发现第一维可以省略。
时间复杂度$O(n^2)$

加强版 加强版

$n\le 100000$
考虑求出Polya定理的生成函数。
这里的颜色数量相当于烷基个数，权重相当于烷基的点数。
置换群为$3$的全排列即$S_3$，显然其循环节指标生成函数为$$Z_{S_3}(t_1,t_2,t_3)=\frac{t_1^3+3t_1{t}_2+2t_3}{6}$$
设答案的生成函数为$F(x)$，则$$F(x)=1+x{Z}_{S_3}(F(x),F(x^2),F(x^3))$$
所以有$$F(x)=1+x\frac{F(x{)}^3+3F(x^2)F(x)+2F(x^3)}{6}$$
如果对Polya的生成函数不熟练，也可以简单地通过求不动点数量来得出答案。
这东西显然可以分治FFT，但同样可以牛顿迭代。
具体来讲就是设$$G(F(x))=1+x\frac{F(x{)}^3+3F(x^2)F(x)+2F(x^3)}{6}-F(x)$$
若当前已求出$$G(H(x))\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{\frac{n}{2}})$$
现在要求$$G(F(x))\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{2}^n)$$
由于$H(x^2)$和$H(x^3)$已经求出，所以将这两项当作常数，然后正常做牛顿迭代即可。
设$B(x)=H(x^2),C(x)=H(x^3)$，最后求出来的式子是$$F(x)=H(x)-\frac{6+x(H(x{)}^3+3B(x)H(x)+2C(x))-6H(x)}{3x(H(x{)}^2+3B(x))-6}$$
时间复杂度$O(n\log n)$

代码（简单版）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
typedef long long LL;
const int N=505;
const int MOD=1000000007;
int n,f[N],ny2,ny3;
int ksm(int x,int y)
{
int ans=1;
while (y)
{
if (y&1) ans=(LL)ans*x%MOD;
x=(LL)x*x%MOD;y>>=1;
}
return ans;
}
int get(int x,int y)
{
if (y==2) return (LL)((LL)x*x%MOD+x)*ny2%MOD;
else return ((LL)x*(x-1)%MOD*(x-2)%MOD*ny3%MOD+(LL)x*(x-1)%MOD+(LL)x)%MOD;
}
int main()
{
scanf("%d",&n);
ny2=ksm(2,MOD-2);
ny3=ksm(6,MOD-2);
f[0]=f[1]=1;
for (int i=2;i<=n;i++)
for (int j=0;j<i;j++)
for (int k=j;k+j<i;k++)
{
int l=i-j-k-1;
if (l<k) continue;
if (j==k&&k==l) (f[i]+=get(f[j],3))%=MOD;
else if (j==k) (f[i]+=(LL)get(f[j],2)*f[l]%MOD)%=MOD;
else if (k==l) (f[i]+=(LL)get(f[k],2)*f[j]%MOD)%=MOD;
else (f[i]+=(LL)f[j]*f[k]%MOD*f[l]%MOD)%=MOD;
}
printf("%dn",f[n]);
return 0;
}

代码（加强版）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
typedef long long LL;
const int N=5005;
const int MOD=1000000007;
int n,ny2,ny6,f[N][4];
int ksm(int x,int y)
{
int ans=1;
while (y)
{
if (y&1) ans=(LL)ans*x%MOD;
x=(LL)x*x%MOD;y>>=1;
}
return ans;
}
int F(int n)
{
int ans=0;
for (int i=0;i<=4;i++) (ans+=f[n][i])%=MOD;
return ans;
}
int get(int x,int y)
{
if (y==1) return x;
else if (y==2) return (LL)((LL)x*x%MOD+x)*ny2%MOD;
else return ((LL)x*(x-1)%MOD*(x-2)%MOD*ny6%MOD+(LL)x*(x-1)%MOD+(LL)x)%MOD;
}
int main()
{
scanf("%d",&n);
ny2=ksm(2,MOD-2);
ny6=ksm(6,MOD-2);
f[1][0]=1;
for (int i=1;i<n;i++)
{
for (int j=n;j>i;j--)
for (int k=1;k<=3;k++)
for (int l=1;l<=k&&l*i+k-l<j;l++)
(f[j][k]+=(LL)get(F(i),l)*f[j-i*l][k-l]%MOD)%=MOD;
}
printf("%dn",F(n));
return 0;
}

代码（加强版 加强版）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#define pb push_back
typedef long long LL;
const int N=100005;
const int MOD=998244353;
int n,L,rev[N*4],A[N*4],B[N*4],C[N*4],a[N*4],D[N*4],E[N*4],tmp[N*4],inv[N*4];
std::vector<int> wn1[25],wn2[25];
int ksm(int x,int y)
{
int ans=1;
while (y)
{
if (y&1) ans=(LL)ans*x%MOD;
x=(LL)x*x%MOD;y>>=1;
}
return ans;
}
void pre(int n)
{
int lg=0;
for (L=1;L<n;L<<=1,lg++);
for (int i=0;i<L;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
}
void NTT(int *a,int f)
{
for (int i=0;i<L;i++) if (i<rev[i]) std::swap(a[i],a[rev[i]]);
for (int i=1,lg=0;i<L;i<<=1,lg++)
for (int j=0;j<L;j+=(i<<1))
for (int k=0;k<i;k++)
{
int u=a[j+k],v=(LL)a[j+k+i]*(f==1?wn1[lg][k]:wn2[lg][k])%MOD;
a[j+k]=(u+v)%MOD;a[j+k+i]=(u+MOD-v)%MOD;
}
if (f==-1) for (int ny=ksm(L,MOD-2),i=0;i<L;i++) a[i]=(LL)a[i]*ny%MOD;
}
void get_inv(int *a,int n)
{
if (n==1) {inv[0]=ksm(a[0],MOD-2);return;}
get_inv(a,n/2);
pre(n*2);
for (int i=0;i<L;i++) tmp[i]=0;
for (int i=0;i<n;i++) tmp[i]=a[i];
for (int i=n/2;i<L;i++) inv[i]=0;
NTT(tmp,1);NTT(inv,1);
for (int i=0;i<L;i++) inv[i]=(inv[i]*2%MOD+MOD-(LL)inv[i]*inv[i]%MOD*tmp[i]%MOD)%MOD;
NTT(inv,-1);
}
void solve(int n)
{
if (n==1) {a[0]=1;return;}
solve(n/2);
pre(n*2);
for (int i=0;i<L;i++) A[i]=B[i]=C[i]=D[i]=E[i]=0;
for (int i=0;i<n/2;i++) B[i*2]=C[i*3]=a[i];
NTT(a,1);
for (int i=0;i<L;i++) A[i]=(LL)a[i]*a[i]%MOD;
NTT(A,-1);
D[0]=6;
for (int i=1;i<n;i++) D[i]=MOD-(LL)3*(A[i-1]+B[i-1])%MOD;
for (int i=0;i<n;i++) E[i]=((LL)A[i]+(LL)3*B[i])%MOD;
get_inv(D,n);
NTT(E,1);
for (int i=0;i<L;i++) E[i]=(LL)E[i]*a[i]%MOD;
NTT(E,-1);NTT(a,-1);
for (int i=n-1;i>=1;i--) E[i]=((LL)E[i-1]+(LL)MOD+(LL)C[i-1]*2)%MOD;
E[0]=6;
for (int i=0;i<n;i++) E[i]=(E[i]+MOD-(LL)a[i]*6%MOD)%MOD;
for (int i=n;i<L;i++) inv[i]=E[i]=0;
NTT(inv,1);NTT(E,1);
for (int i=0;i<L;i++) E[i]=(LL)inv[i]*E[i]%MOD;
NTT(E,-1);
for (int i=0;i<n;i++) a[i]=(a[i]+MOD+E[i])%MOD;
}
void pre_wn()
{
for (int i=0;i<20;i++)
{
int w1=ksm(3,(MOD-1)/(1<<(i+1))),w2=ksm(3,MOD-1-(MOD-1)/(1<<(i+1)));
wn1[i].pb(1);wn2[i].pb(1);
for (int j=1;j<(1<<i);j++) wn1[i].pb((LL)wn1[i][j-1]*w1%MOD),wn2[i].pb((LL)wn2[i][j-1]*w2%MOD);
}
}
int main()
{
scanf("%d",&n);
int len=1;
for (;len<=n;len<<=1);
pre_wn();
solve(len);
printf("%dn",a[n]);
return 0;
}

最后

以上就是魔幻皮带为你收集整理的【LibreOJ 6269&6269&6538 烷基计数 加强版 加强版】【生成函数+牛顿迭代】题意简单版加强版加强版 加强版代码（简单版）代码（加强版）代码（加强版 加强版）的全部内容，希望文章能够帮你解决【LibreOJ 6269&6269&6538 烷基计数 加强版 加强版】【生成函数+牛顿迭代】题意简单版加强版加强版 加强版代码（简单版）代码（加强版）代码（加强版 加强版）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。