自动搬运

查看原文

来自洛谷，原作者为

	zhouyuhang Bénédiction de Dieu dans la solitude

搬运于2025-08-24 23:03:53，当前版本为作者最后更新于2024-08-08 19:57:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先对问题进行转化。构造 $n + m$ 个点的有向图 $G$：将 $(x, y, R)$ 操作视为向 $G$ 中加入 $y + n \to x$ 的有向边，将 $(x, y, C)$ 视为加入 $x \to y + n$ 的有向边，并要求在每次加边时两端点入度均为 $0$。此时，$k$ 即为 $G$ 的边数，答案即为 $G$ 的数量。接下来，我们将借助这一构造说明 $k = n + m - 1$。

首先说明 $k \le n + m - 1$。将 $G$ 视作无向图，下面将说明，$G$ 中必然不存在环。考虑反证，如果图中存在环 $(C_1, C_2), (C_2, C_3), \cdots, (C_k, C_1)$，不妨设 $(C_1, C_2)$ 的方向为 $C_1 \to C_2$，那么 $(C_2, C_3)$ 的方向就只能为 $C_2 \to C_3$，否则 $C_1 \to C_2$ 与 $C_3 \to C_2$ 无论谁先谁后都会导出矛盾……以此类推，一直到 $(C_k, C_1)$ 的方向只能为 $C_k \to C_1$。不妨设 $(C_1, C_2)$ 是环中最后一个被操作的边，在它被操作前，$(C_k, C_1)$ 已经被定向为 $C_k \to C_1$，$C_1$ 的入度不为 $0$，从而导出矛盾。因此，将 $G$ 视为无向图后其中不存在环，即有 $k \le n + m - 1$。

接下来说明 $k = n + m - 1$ 能够取到。此时将 $G$ 视为无向图，其必然为一棵树。而在刚刚的证明过程中，我们发现，在最终的定向结果中，不能同时存在 $x \to z$ 和 $y \to z$ 这样的两条边。这也就意味着最终每个点的入度都不超过 $1$。而入度的总和为 $n + m - 1$，这就说明恰有 $1$ 个点（记其为 $x$）入度为 $0$，剩余的点入度恰为 $1$——实际上，这就是一颗以 $x$ 为根的外向树。而对于这样一颗外向树，我们只需不断操作叶子结点的连边，即可满足连边时两端点入度为 $0$ 的限制。因此，每一棵外向树都是可行的，$k$ 自然可以取到 $n + m - 1$。

至此，我们已经可以顺理成章地得到计数做法。注意到在外向树根节点的选择中，每个点都是可行的，因此每颗树都可以衍生出 $(n + m)$ 个不同的外向树。哪些树是可行的呢？不难发现，$K_{n, m}$ 的每一颗生成树均可行。而 $K_{n, m}$ 的生成树个数是一个经典问题，展开行列式即可知其答案为 $n ^ {m - 1} m ^ {n - 1}$，故原问题答案即为 $f(n, m) = (n + m) n ^ {m - 1} m ^ {n - 1}$。预处理 $i ^ j$ 并计算，复杂度即为 $O(nm)$。

本题也存在一些高复杂度的更加复杂的做法，欢迎大家在题解区分享。