【统一省选2024】虫洞 - 题目 - Universal Online Judge

E 国有 $n$ 个城市，编号为 $1$ 至 $n$ 。为了让城市之间的来往更加便利，E 国的交通部想在 $n$ 个城市间建造一些虫洞。每条虫洞是一条单向的从某个城市到另一个城市的通道。允许通道的起点和终点是同一个城市，也允许两个城市之间有多个虫洞连接。

为了区分虫洞的建造时间，交通部给每一条虫洞一个正整数的编号。

我们称一种虫洞的建造方案是好的，若它满足如下四个条件：

存在一个非负整数 $d$ 使得每个城市恰好是 $d$ 条虫洞的起点，也恰好是 $d$ 条虫洞的终点。
对于每个城市而言，在以它为起点的虫洞的编号中， $1$ 到 $d$ 恰好各出现一次。
对于每个城市而言，在以它为终点的虫洞的编号中， $1$ 到 $d$ 恰好各出现一次。
任意选取一个城市 $u$ 和正整数 $1 \leq j_{1}, j_{2} \leq d$ 。设从 $u$ 出发，先经过一次编号为 $j_{1}$ 的虫洞，再经过一次编号为 $j_{2}$ 的虫洞，到达城市 $v_{1}$ 。设从 $u$ 出发，先经过一次编号为 $j_{2}$ 的虫洞，再经过一次编号为 $j_{1}$ 的虫洞，到达城市 $v_{2}$ 。则条件 $v_{1} = v_{2}$ 必定满足。

特别地，不建造任何虫洞的方案也是好的。

现在，建造师已建造了 $m n$ 条虫洞，且给了它们 $1 \sim m$ 的编号，此时这样的建造方案是好的。他想要新建造 $k n$ 条虫洞，并给它们 $(m + 1) \sim (m + k)$ 的编号。他必须保证这 $(m + k) n$ 条虫洞形成的建造方案仍然是好的。他想知道有多少种新建造 $k n$ 条虫洞的方法，使得这 $(m + k) n$ 条虫洞形成的建造方案是好的。

由于答案很大，你只需要求出方案数除以 $998244353$ 的余数。

输入格式

输入的第一行四个非负整数 $c, n, m, k$ ，其中 $c$ 表示测试点编号。样例中的 $c$ 表示该样例的数据范围与第 $c$ 个测试点的数据范围相同。

接下来 $n m$ 行，每行三个正整数 $u, v, w$ ，表示一条编号为 $w$ 的，起点为 $u$ 号城市，终点为 $v$ 号城市的虫洞。

输出格式

输出一行整数，表示方案数除以 $998244353$ 的余数。

样例 1

input

output

explanation

在该组样例中，已经建造的编号为 $1$ 的虫洞为 $1 \to 2, 2 \to 1, 3 \to 4, 4 \to 3$ 。为了使 $8$ 条虫洞形成的建造方案是好的，新建造的编号为 $2$ 的虫洞可能有 $8$ 种情形：

$1 \to 1, 2 \to 2, 3 \to 3, 4 \to 4$
$1 \to 1, 2 \to 2, 3 \to 4, 4 \to 3$
$1 \to 2, 2 \to 1, 3 \to 3, 4 \to 4$
$1 \to 2, 2 \to 1, 3 \to 4, 4 \to 3$
$1 \to 3, 2 \to 4, 3 \to 1, 4 \to 2$
$1 \to 3, 2 \to 4, 3 \to 2, 4 \to 1$
$1 \to 4, 2 \to 3, 3 \to 1, 4 \to 2$
$1 \to 4, 2 \to 3, 3 \to 2, 4 \to 1$

【样例 2】

见附件中的 wormhole2.in/ans。

该样例的 $c = 2$ ，它满足第 2 个测试点的限制条件。

【样例 3】

见附件中的 wormhole3.in/ans。

该样例的 $c = 5$ ，它满足第 5 个测试点的限制条件。

【样例 4】

见附件中的 wormhole4.in/ans。

该样例的 $c = 7$ ，它满足第 7 个测试点的限制条件。

【样例 5】

见附件中的 wormhole5.in/ans。

该样例的 $c = 9$ ，它满足第 9 个测试点的限制条件。

【样例 6】

见附件中的 wormhole6.in/ans。

该样例的 $c = 11$ ，它满足第 11 个测试点的限制条件。

【样例 7】

见附件中的 wormhole7.in/ans。

该样例的 $c = 15$ ，它满足第 15 个测试点的限制条件。

【样例 8】

见附件中的 wormhole8.in/ans。

该样例的 $c = 17$ ，它满足第 17 个测试点的限制条件。

【样例 9】

见附件中的 wormhole9.in/ans。

该样例的 $c = 20$ ，它满足第 20 个测试点的限制条件。

【样例 10】

见附件中的 wormhole10.in/ans。

该样例的 $c = 22$ ，它满足第 22 个测试点的限制条件。

子任务

对于所有测试点，

$1 \leq n \leq 2 \cdot 10^{3}$ ， $0 \leq m \leq 10^{3}$ ， $1 \leq k \leq 10^{15}$ ；
$1 \leq u, v \leq n$ ， $1 \leq w \leq m$ ；
保证初始建造的 $m n$ 条虫洞构成一个号的建造方案。

测试点编号	$n$	$m$	$k$
$1 \sim 4$	$\leq 5$	$\leq 3$	$\leq 3$
$5 \sim 6$	$\leq 2 \cdot 10^{3}$	$= 0$	$= 1$
$7 \sim 8$	$\leq 10^{2}$	$= 1$	$= 1$
$9 \sim 10$	$\leq 10^{2}$	$\leq 10$	$= 1$
$11 \sim 14$	$\leq 10^{2}$	$\leq 10$	$\leq 10^{3}$
$15 \sim 16$	$\leq 10^{2}$	$= 0$	$\leq 10^{15}$
$17 \sim 19$	$\leq 10^{2}$	$\leq 10$	$\leq 10^{15}$
$20 \sim 21$	$\leq 2 \cdot 10^{3}$	$\leq 10^{3}$	$\leq 10^{2}$
$22 \sim 25$	$\leq 2 \cdot 10^{3}$	$\leq 10^{3}$	$\leq 10^{15}$

【提示】

本题部分测试点输入规模较大，我们推荐你使用较为快速的读入方式。

时间限制： $2s$

空间限制： $512MB$

Universal Online Judge

UOJ

#867. 【统一省选2024】虫洞