鸽子更博了！
如今大学已尘埃落定，终于成功进入清华，不过不在计算机系。还是希望将(OI)作为一种爱好，也想找机会参加(acm)，因此还是会时不时复健一下。这一题是我记忆中攻克最艰难、解题后也最痛快的一题，因此印象深刻。当然我早已忘了具体的步骤，因此最近重做了一遍，也算是对自己的魔鬼训练吧。
与群论相关的前置知识：
设(G)是所有长度为(n)的置换构成的群，(X)是一些长度为(n)的序列构成的集合。如果将(G)作用于(X)，那么：
对于(xin X)，称({yin X|y=f(x),fin G})为(x)的轨道，记为(Orbit(x))，对于(yin Orbit(x))，称(y)为(x)的等价类。
对于(xin X)，称({fin G|x=f(x)})为(x)的稳定化子，记为(SG(x))。
对于(fin G)，称({xin X|x=f(x)})为(f)的不动点，记为(fix(f))。
与题意类似，我们定义两个森林同构，当且仅当可以通过某种一一对应关系，使得一个森林的任意一棵树都和另一森林对应的树同构。
设(cnt_n)为(n)个点的无标号有根树个数，并令所有树从(1)到(cnt_n)标号。
那么令(S_{n,i})表示所有按照题目要求构造的带标号有根树中，与(n)个点的(i)号无标号有根树同构的那一部分构成的集合。
由于按照题意建立的(n)个点的树共有((n-1)!)种，因此$$ans=frac{1}{(n-1)!^k}sum_{i=1}^{cnt_n}|S_{n,i}|^k$$
那么重点关注后半部分，尝试利用动态规划的方法解题。那么令：
考虑如何转移。回想判断无标号有根树同构的过程：先将根的所有子树按照一定规则排序，逐一比较即可。那么是否可以先枚举排序后在最后的子树，将其删去递归求解，再考虑这棵子树的贡献呢？
但是，如果枚举排在最后的子树，那么就隐含了条件：对于递归的树，其根的所有子树的优先级一定在该子树之前（或者就是该子树），而子树的数目众多，无法比较好的设计状态。
但这样的思考并不是毫无意义的。虽然枚举最后的子树不太现实，但也许可以退而求其次，对子树先进行一个“粗略的划分”，而非直接一个个分离。不难想到先根据子树大小从小到大初步排序，每次删去大小最大的那一批子树，对剩余的树进行递归求解，再考虑这些相同大小的子树的贡献。那么对递归求解的树的额外要求，就转变为了根的子树大小不能超过某个值，不仅状态大量减少，考虑起来也非常方便。
那么为了方便，我们记(mxs(S_{n,i}))表示对于集合(S_{n,i})中的树，他们根的子树的最大大小，类似记(mns(S_{n,i}))表示最小的。根据上面的想法，可以设计辅助状态：
则有(dp_n=tmp_{n,n-1})。再考虑状态的转移。那么就枚举大小为(p)的根的子树的数目，分配标号，再将前后部分独立考虑。前半部分可以递归到之前的状态，但后半部分无法递归，需要单独解决，表示成式子，就是：
因为(1)号点显然是根，所以实际分配的标号只有(n-1)个。其中：
表示需要单独解决的那一部分。之所以大小为(u*p+1)，是因为我们给着(u)棵大小为(p)的树额外加了一个形式上的根，方便考虑问题。那么第一步先考虑标号的分配。
按照常规来讲，标号的分配应该是({u*pchoose p,p,dots,p})种情况，但在此处，由于根的所有子树之间是没有顺序的（这也是之前进行“粗略的划分”遗留下来的问题），因此如果出现两棵相同的子树，它们的地位完全等价，也即即使赋予它们的标号互换，得到的也是同一种结果。但是({u*pchoose p,p,dots,p})的分配方式显然将互换前后看作不一样的。
看来({u*pchoose p,p,dots,p})并不能适用于所有情况，还需要进行进一步的分类讨论。那么我们假设其中某一个(S_{u*p+1,i})，其根的子树可以分为(m)类本质不同的，且数目分别为(a_1,a_2,a_3,dots,a_mBig((sum_{t=1}^ma_t)=uBig))，也不妨将(a)不降序排序。对于同一类的子树内部，任意两棵树都可以互换标号，因此分配给这一类的(a_t)组标号彼此是无序的，需要将分配标号方案数乘以(frac{1}{a_t!})。因此对这一情况，分配的方法数应该为：
初步解决分配标号的问题后，我们再考虑下一步操作。此时只要将(u)棵子树内部的标号都看作是(1,2,dots,p)即可，此时可以去掉形式上的根，将其转化为(u)棵树的森林。根据之前的定义，我们可以将全体大小为(p)的无标号有根树编号为(1,2,dots,cnt_p)。对于某一个森林，将其每一棵树对应到这棵树所属类别的编号，我们可以将该森林与一个无序可重集合(widetilde x)对应。将所有(widetilde x)组成的集合记作(widetilde X)。
则(widetilde x)满足两个性质：恰好包含(u)个数，且每个数都在(1)到(cnt_p)之间。也可以将(a_t)的概念从(S_{u*p+1,i})迁移到(widetilde x)上。不妨记(omega_{widetilde x})为属于(widetilde x)对应森林的带标号森林的数目的(k)次幂，那么(f_{p,u})可以表示为：
因为在分配完标号以后，树的同构就转化为了森林的同构。
然而，由于(widetilde x)是无序可重集合，这非常不利于枚举，因此直接进行计算也非常麻烦。希望能将其转化为有序可重集合（即一个长度为(u)的序列）再进一步解决问题。
那么设(x)是一个长度为(u)的序列，且每一个数都在(1)到(cnt_p)之间。将所有这样的(x)的集合记做(X)。如果(x)无序化后能和某一个(widetilde x)相同，我们称(x)对应到(widetilde x)。
由于(widetilde x)是一个可重的集合，因此对应到(widetilde x)的(x)的数目是变化的，不能直接枚举(x)。想要利用(X)得到一个和((*))相类似的等式，还需要借助置换群。
为了表达方便，用前置知识中的术语来表达。设(G)是所有长度为(u)的置换构成的群，将(G)作用于(X)。
那么对于一个(Orbit(x))，所有在这一集合内的(y)都对应到相同的(widetilde x)，可以用(Orbit(x))来代替(widetilde x)。将(a_t)、(omega)的概念迁移到(x)上，我们可以得到与((*))类似的式子：
不难发现(|Orbit(x)|=frac{u!}{prod_{t=1}^ma_t!})。此时有一个难点，就是(omega_x)的计算。先尝试将所有(a)相同的(x)发在一起计算（此时(igg(prod_{t=1}^mfrac{1}{a_t!^k}igg))和(|Orbit(x)|)是相同的）。也就是说，此时的森林要求有(m)种不同的树，第(i)种(a_i)棵。首先考虑(m=1)的情况，也就是需要(u)棵同构的树，不难发现这就等同于：
看上去似乎并未计算过这个式子，为了计算可能需要修改状态。那么先搁置一边，考虑(m>1)的情况，我们能否直接用下面的式子：
计算呢？不可行，因为这并不能排除不同的两组得到同一类树的情况，同时也没有考虑组与组的数目相同时地位等价的问题。
但这样的思考并不是毫无意义的。不难发现，如果组与组之间默认为地位不等，且不同的组可以使用相同的一类树，那么((**))就是正确的。
最关键的一点是，这两个条件似乎与某一置换下的不动点有异曲同工之妙。我们考虑(fin G)，则(fix(f))就是(f)的不动点集合。(f)是由若干个置换环组成的，设有(m')个置换环，并设置换环的大小分别为(a'_1,a'_2,dots,a'_{m'})。可以发现，如果(x)是(f)的不动点，那么有与之前的(a)类似的性质，同一置换环内的位置上，树的种类必须相同。但是，由于置换环本身位置不同，每个置换环就是地位不等的（这也是有序序列的一个好处）。并且，由于我们只要求其为不动点即可，并不需要每个置换环的树种类各不相同，这就完美的符合我们之前的两个条件。
因此我们就可以利用((**))了，也就是说：
不过还有一个问题没有解决：怎么求(sum_{i=1}^{cnt_p}|S_{p,i}|^{a'_t*k})？它的形式和(dp_p)相似，但是指数增加了(a'_t)倍。必须先进一步扩张状态才能解决这个问题。
那么增加一个指标(j)，表示指标扩张的倍数。即：
相应修改转移方程：
则：
注意(omega_x)也是和(j)相关的。
首先考虑一下状态数量问题，可以发现由于(a'_tleq frac{n}{p})，因此这两维的乘积不会超过全局的(n)，因此只有(sum_{i=1}^{n}lfloorfrac{n}{i} floor=O(nlog n))种可能。
还有一个问题是，我们并不只是简单的求(sum_{xin X}omega_x)，而是有一个(Big(prod_{t=1}^mfrac{1}{a_t!^{j*k}}Big)*frac{1}{|Orbit(x)|})的系数，不能这样直接交换求和顺序。
那要通过什么方式转化呢？我们设置换(f)的某个权值为(w_f)，那么有如下等式：
只是交换了求和顺序，显然成立。这个等式的左边和(sum_{xin X}igg(prod_{t=1}^mfrac{1}{a_t!^{j*k}}igg)*frac{omega _x}{|Orbit(x)|})相似，右边和(sum_{xin fix(f)}omega_x)相似，尝试利用这个等式来对目标进行转化。
如果能找到某种权重函数(w)，使得等式：
成立，其中(C)是一个常数，那么就有：
由于后方的连乘只和置换环大小情况有关，那么自然也希望权重函数也之和置换环大小有关，而且最好也是连乘形式，即：
如果可行，那么可以继续转化((***))式：
则每个置换的结果都只和其置换环分解的大小分布情况有关，可以换一种求和方式，令(h_i={widetilde w}_{i}*dp_{p,i*j})，枚举置换环的大小分布，并分配标号：
似乎转化为了熟悉的式子。设生成函数(H(x)=sum_{i>0}frac{h_i}{i}x^i)，那么前面的式子就转化为：
好的！也就是说，我们现在有：
唯一的问题就是计算权重函数(widetilde w)了。回顾一下，我们是希望满足这个等式：
展开(|Orbit(x)|)，即：
对于(x)，它的稳定化子就是满足仅在相同种类树之间进行置换的集合，就是说，只能在同种树内部进行置换环的拆解。那么模仿之前对置换环的枚举方法，换一种方式计算等式左边的值，只是换成了在每一类树内部：
同之前，设(W(x)=sum_{i>0}frac{{widetilde w}_i}{i}x^i)，那么上方等式继续转化：
带回原等式，即为：
消去(prod_{t=1}^{m}a_t!)：
显然我们令(C=u!)，那么有([x^i]e^{W(x)}=frac{1}{i!^{j*k}})，(e^{W(x)})就是一个已知的多项式。通过(W(x)=ln e^{W(x)})就可以求解出(widetilde w)了。
回顾一下过程，可以计算出复杂度是(O(n^2log n))。由于多项式(ln)和(exp)不是瓶颈，可以用简洁的(O(n^2))算法来计算。