AGC068E 题解

· · 题解

这个 A_{x_i,y_i} 的形式就很像是图上的一条边，所以我们将 A 看作一个有向完全图的邻接矩阵，(x_i,y_i) 看作边 y_i\to x_i（这里不用 x_i\to y_i 是为了后面证明方便，不过直接连 x_i\to y_i 应该是类似的），然后发现一组 (x,y) 的权值就是所有 (y_i,x_i) 的边权之积。由于 y 是 x 的置换，所以这张 y_i\to x_i 连出来的图的每个连通块都是一个欧拉图。注意到欧拉回路相对来说是比较好处理的，因为可以直接一步一步向后走并进行 dp，所以我们希望找到原问题和欧拉回路之间的联系。

我们发现对于一张连出来的图，可以给每个点的出边钦定一个顺序，例如假设某个数在 y_{i_1},y_{i_2},\cdots,y_{i_k} 这些位置出现了，则我们认为它连出去的 k 条边按顺序依次连向 x_{i_1},x_{i_2},\cdots,x_{i_k}。显然一个序列 x 只会对应一张图以及边的排列顺序，那么是否确定了一张图和边的顺序之后就能唯一还原系列 x 呢？首先若给定了这张图那么首先可以确定 y，因为它只和每个元素的出现次数有关。接着我们从 1 出发按照求欧拉回路的方式 dfs 遍历整张图，由于每个元素对应的 i_1,i_2,\cdots,i_k 已知，所以我们每遍历一条边就可以根据其顺序确定出现所在的位置，因此就唯一还原了原序列。

既然我们已经建立了双射，便只需要对这样的图和出边顺序计数即可。而由于这样的一个顺序和欧拉回路的遍历顺序也是一一对应的，所以我们只需要对欧拉回路计数即可。为了避免算重，我们从 1 出发一直到第一次回到 1 结束作为一个循环，然后下一次可以继续从 1 出发，也可以从更大的点出发。但不能从一个更小的点出发，否则会算重。而计算所有欧拉回路的边权之积的和只需要 dp 记录路径起点和终点即可。

最后一个问题就是我们需要回答 x_1=k 的答案，而 x_1 就是第一条出边，所以我们倒着对欧拉回路 dp，在最后一步合并的时候统计答案即可。复杂度 O(n^4)。

代码