题解

思路

一次变化选中一条边，并在这条边的两个端点之间加入一条长度为二的新路径。最终世界可以递归地看成若干个并联结构；每个新增顶点对应两个串联子世界。

令 $f_{i,j}$ 表示从一条初始边开始，进行 $i$ 次变化后得到最小割为 $j$ 的不相似世界数量。再令 $g_{i,j}$ 表示一个新增顶点及其两侧子世界一共使用 $i$ 次变化、该串联结构最小割为 $j$ 的数量。

两个子世界串联时，最小割取两者的较小值；若干串联结构与初始边并联时，最小割容量相加。

做法

计算 $g_{i,j}$ 时，枚举左侧使用 $k$ 次变化，右侧使用 $i-1-k$ 次变化。两侧最小割的较小值为 $j$。

为优化“较小值”卷积，记

则串联结构最小割至少为 $j$ 的数量为

因此 $g_{i,j}=H_{i,j}-H_{i,j+1}$。

接下来把所有串联结构作为无序多重集合并联起来。若某个类别 $(i,j)$ 中共有 $g_{i,j}$ 种不同结构，恰好取 $q$ 个该类别结构的无序多重集合数量为

按 $(i,j)$ 的字典序依次进行多重背包，变化次数增加 $qi$，最小割增加 $qj$。组合数可用递推式逐项乘上 $(g_{i,j}+q-1)/q$，所有除法使用模逆元。

初始状态为 $f_{0,1}=1$，其中容量一来自始终保留的初始边。逐行计算 $g$、背包更新 $f$，再生成新一行后缀和即可。

子任务 1 直接枚举每一步选择的边。对每个结果固定 $s,t$，枚举其余顶点置换并取邻接位串的最小表示，以此去除同构；最后枚举割的两侧分配求最小割。

子任务 2 不使用后缀和，直接枚举左右子世界的两个最小割值并取较小值，之后执行相同的无序多重背包。

正确性证明

每个最终世界相对于初始边，都唯一对应于若干种串联结构的无序多重集合：选择初始边产生的新增顶点给出顶层并联结构，而该顶点两侧分别递归形成两个子世界。顶层结构没有顺序，因此多重集合计数恰好消除同构产生的排列重复。

串联结构中断开 $s,t$ 只需断开两侧之一，所以其最小割是两侧最小割的较小值；并联结构必须分别断开每个分支以及初始边，所以容量相加。由此，$g$ 的较小值卷积和 $f$ 的多重背包分别准确计算串联与并联组合。

后缀和 $F_{i,j}$ 准确统计最小割至少为 $j$ 的子世界。两侧都至少为 $j$ 当且仅当串联结构至少为 $j$，相邻后缀差便得到最小割恰为 $j$ 的数量。因此优化没有改变 $g$ 的含义。

按类别顺序进行多重背包时，每个无序多重集合只在其各类别使用次数对应的唯一转移中出现一次。故最终 $f_{n,m}$ 当且仅当计数所有满足要求的不相似世界。

复杂度

子任务 1 的复杂度由可达图枚举、至多 $n!$ 次同构规范化和 $2^n$ 次割枚举构成，适用于 $n\le6$。

子任务 2 直接枚举较小值卷积，时间复杂度为 $O(n^5)$，空间复杂度为 $O(n^2)$。

完整算法使用后缀和优化卷积，并执行二维多重背包，时间复杂度上界为 $O(n^4\log n)$，空间复杂度为 $O(n^2)$。