题目传送门：洛谷 P5564。
题意简述：
有 (n) 个点，染 (m) 种颜色，第 (i) 种颜色染恰好 (cnt_i) 个节点，满足 (cnt_1+cnt_2+cdots+cnt_m=n)。
求这 (n) 个点组成的本质不同的无标号+有序（子树有序）基环（环长至少为 (2)）树个数。
两棵基环树本质相同当且仅当通过环的旋转（不能翻转）后能使得它们完全相同。
题解：
首先考虑只染一种颜色的 (n) 个点（(nge1)）的无标号有根有序树个数计数。
考虑这棵树的括号序，发现其括号序是长度为 (n) 的合法括号串，但是必须满足最外层括号（根节点）只有一对。
即 (n) 个点的有根有序树个数为 (n-1) 对括号组成的合法括号串，即第 (n-1) 个卡特兰数。
令 (n) 个点的有根有序树个数为 (t_n)，令其 OGF 为 (displaystyle T=sum_{i=1}^{+infty}t_ix^i)，即 (T=xC)，其中 (C) 为卡特兰数的 OGF。
再考虑染色的问题，不难发现只要有序，则染色和树形态是相互独立的。
即只要乘上一个多重组合数 (displaystyleinom{n}{cnt_1,cnt_2,ldots,cnt_m}) 即可。
回到原问题，枚举环长 (k)，使用 Burnside 引理统计等价类个数。环的旋转置换的统计方法是常见的，即枚举因数 (d)，等价于循环 (d) 格的置换个数为 (varphi!left(dfrac{k}{d}
ight))。则有：
[egin{aligned}mathbf{Ans}&=sum_{k=2}^{n}dfrac{1}{k}sum_{d|k}varphi!left(dfrac{k}{d}
ight)!cdot f(d)end{aligned}
]
其中 (f(d)) 表示循环 (d) 格时的不动点个数。
循环 (d) 格时，存在 (d) 个长度为 (dfrac{k}{d}) 的循环，循环内的每个元素都代表一棵外向树。为了方便进一步的展开，交换 (d) 与 (dfrac{k}{d}) 的意义，枚举 (d) 为循环长度，而 (dfrac{k}{d}) 为循环个数。此时每个循环内的树形态相互独立，而且染色和树形态相互独立，但每个循环的树形态必须相同，且染色也必须相同，也就是说有 (dfrac{k}{d}) 棵树，且总点数为 (dfrac{n}{d})，并且需要满足每种颜色的个数是 (d) 的倍数，即 (left.d:middle|:gcdlimits_{i=1}^{m}cnt_i
ight.)。则公式变为：
[egin{aligned}mathbf{Ans}&=sum_{k=2}^{n}dfrac{1}{k}sum_{d|k}varphi(d)cdot f!left(dfrac{k}{d}
ight)!\&=sum_{k=2}^{n}dfrac{1}{k}sum_{d|k}varphi(d)cdot!left{!left[d:middle|:gcdlimits_{i=1}^{m}cnt_i
ight]!cdot!left[x^{n/d}
ight]!T^{k/d}cdotinom{n/d}{cnt_1/d,cnt_2/d,ldots,cnt_m/d}
ight}!end{aligned}
]
此时有两条路可走，其一是留下生成函数 (T) 的形式不变，其二是考虑使用卡特兰数的性质。
先使用第一种做法，考虑交换求和顺序并改变求和指标 (k) 为 (kd)：
[egin{aligned}mathbf{Ans}&=sum_{k=2}^{n}dfrac{1}{k}sum_{d|k}varphi(d)cdot!left{!left[d:middle|:gcd_{i=1}^{m}cnt_i
ight]!cdot!left[x^{n/d}
ight]!T^{k/d}cdotinom{n/d}{cnt_1/d,cnt_2/d,ldots,cnt_m/d}
ight}!\&=-t_ninom{n}{cnt_{1ldots m}}+sum_{dmidgcd_{i=1}^{m}cnt_i}varphi(d)cdotinom{n/d}{cnt_{1ldots m}/d}cdot!left[x^{n/d}
ight]!sum_{k=1}^{n/d}frac{T^k}{kd}\&=-t_ninom{n}{cnt_{1ldots m}}+sum_{dmidgcd_{i=1}^{m}cnt_i}frac{varphi(d)}{d}cdotinom{n/d}{cnt_{1ldots m}/d}cdot!left[x^{n/d}
ight]!sum_{k=1}^{+infty}frac{T^k}{k}\&=-t_ninom{n}{cnt_{1ldots m}}+sum_{dmidgcd_{i=1}^{m}cnt_i}frac{varphi(d)}{d}cdotinom{n/d}{cnt_{1ldots m}/d}cdot!left[x^{n/d}
ight]!(-ln(1-T))end{aligned}
]
第二行的第一项是因为后面统计了 (d=k=1) 的情况，但是实际不需要，所以要减掉。
最后一行利用了 (ln) 在 (1) 处展开的的泰勒级数：(displaystyleln(1-x)=-sum_{i=1}^{+infty}frac{x^i}{i})。
先使用多项式对数函数计算出 (-ln(1-T))，按照此式直接计算即可。时间复杂度 (mathcal{O}(nlog n+sigma_0(n)cdot m))。
第二种做法是考虑卡特兰数和自身的 (m) 次卷积的第 (n) 项的通项。
有公式 (displaystyle[x^n]C^m=inom{2n+m-1}{n}-inom{2n+m-1}{n-1})，将此式代入可得：
[egin{aligned}mathbf{Ans}&=sum_{k=2}^{n}dfrac{1}{k}sum_{d|k}varphi(d)cdot!left{!left[d:middle|:gcdlimits_{i=1}^{m}cnt_i
ight]!cdot!left[x^{n/d}
ight]!T^{k/d}cdotinom{n/d}{cnt_1/d,cnt_2/d,ldots,cnt_m/d}
ight}!\&=sum_{k=2}^{n}dfrac{1}{k}sum_{d|k}varphi(d)cdot!left{!left[d:middle|:gcdlimits_{i=1}^{m}cnt_i
ight]!cdot!left(inom{2n/d-k/d-1}{2n/d-2k/d}-inom{2n/d-k/d-1}{2n/d-2k/d-1}
ight)!cdotinom{n/d}{cnt_{1ldots m}/d}
ight}!\&=-t_ninom{n}{cnt_{1ldots m}}+sum_{dmidgcd_{i=1}^{m}cnt_i}frac{varphi(d)}{d}cdotinom{n/d}{cnt_{1ldots m}/d}sum_{k=1}^{n/d}frac{1}{k}!left(inom{2n/d-k-1}{2n/d-2k}-inom{2n/d-k-1}{2n/d-2k-1}
ight)!end{aligned}
]
直接计算即可，复杂度 (mathcal{O}(sigma_0(n)(n+m)))。