{"problem":{"name":"[省选联考 2024] 虫洞","description":{"content":"E 国有 $n$ 个城市，编号为 $1$ 至 $n$。为了让城市之间的来往更加便利，E 国的交通部想在 $n$ 个城市间建造一些虫洞。每条虫洞是一条**单向**的从某个城市到另一个城市的通道。允许通道的起点和终点是同一个城市，也允许两个城市之间有多个虫洞连接。 为了区分虫洞的建造时间，交通部给每一条虫洞一个正整数的编号。 我们称一种虫洞的建造方案是**好的**，若它满足如下四个条件： 1. ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10219"},"statements":[{"statement_type":"Markdown","content":"E 国有 $n$ 个城市，编号为 $1$ 至 $n$。为了让城市之间的来往更加便利，E 国的交通部想在 $n$ 个城市间建造一些虫洞。每条虫洞是一条**单向**的从某个城市到另一个城市的通道。允许通道的起点和终点是同一个城市，也允许两个城市之间有多个虫洞连接。\n\n为了区分虫洞的建造时间，交通部给每一条虫洞一个正整数的编号。\n\n我们称一种虫洞的建造方案是**好的**，若它满足如下四个条件：\n\n1. 存在一个非负整数 $d$ 使得每个城市恰好是 $d$ 条虫洞的起点，也恰好是 $d$ 条虫洞的终点。\n2. 对于每个城市而言，在以它为起点的虫洞的编号中，$1$ 到 $d$ **恰好**各出现一次。\n3. 对于每个城市而言，在以它为终点的虫洞的编号中，$1$ 到 $d$ **恰好**各出现一次。\n4. 任意选取一个城市 $u$ 和正整数 $1\\le j_1, j_2 \\le d$。设从 $u$ 出发，先经过一次编号为 $j_1$ 的虫洞，再经过一次编号为 $j_2$ 的虫洞，到达城市 $v_1$。设从 $u$ 出发，先经过一次编号为 $j_2$ 的虫洞，再经过一次编号为 $j_1$ 的虫洞，到达城市 $v_2$。则条件 $v_1=v_2$ 必定满足。\n\n特别地，不建造任何虫洞的方案也是好的。\n\n现在，建造师已建造了 $mn$ 条虫洞，且给了它们 $1\\sim m$ 的编号，**此时这样的建造方案是好的**。他想要新建造 $kn$ 条虫洞，并给它们 $(m+1)\\sim (m+k)$ 的编号。他必须保证这 $(m + k)n$ 条虫洞形成的建造方案仍然是好的。他想知道有多少种新建造 $kn$ 条虫洞的方法，使得这 $(m + k)n$ 条虫洞形成的建造方案是好的。\n\n由于答案很大，你只需要求出方案数除以 $998244353$ 的余数。\n\n## Input\n\n输入的第一行四个非负整数 $c, n, m, k$，其中 $c$ 表示测试点编号。样例中的 $c$ 表示该样例的数据范围与第 $c$ 个测试点的数据范围相同。\n\n接下来 $nm$ 行，每行三个正整数 $u,v,w$，表示一条编号为 $w$ 的，起点为 $u$ 号城市，终点为 $v$ 号城市的虫洞。\n\n## Output\n\n输出一行整数，表示方案数除以 $998244353$ 的余数。\n\n[samples]\n\n## Note\n\n**【样例 1 解释】**\n\n在该组样例中，已经建造的编号为 $1$ 的虫洞为 $1\\to 2,2\\to 1,3\\to 4,4\\to 3$。为了使 $8$ 条虫洞形成的建造方案是好的，新建造的编号为 $2$ 的虫洞可能有 $8$ 种情形：\n\n1. $1\\to 1, 2\\to 2, 3\\to 3, 4\\to 4$\n2. $1\\to 1, 2\\to 2, 3\\to 4, 4\\to 3$\n3. $1\\to 2, 2\\to 1, 3\\to 3, 4\\to 4$\n4. $1\\to 2, 2\\to 1, 3\\to 4, 4\\to 3$\n5. $1\\to 3, 2\\to 4, 3\\to 1, 4\\to 2$\n6. $1\\to 3, 2\\to 4, 3\\to 2, 4\\to 1$\n7. $1\\to 4, 2\\to 3, 3\\to 1, 4\\to 2$\n8. $1\\to 4, 2\\to 3, 3\\to 2, 4\\to 1$\n\n**【样例 2】**\n\n见附件中的 `wormhole2.in/ans`。\n\n该样例的 $c = 2$，它满足第 2 个测试点的限制条件。\n\n**【样例 3】**\n\n见附件中的 `wormhole3.in/ans`。\n\n该样例的 $c = 5$，它满足第 5 个测试点的限制条件。\n\n**【样例 4】**\n\n见附件中的 `wormhole4.in/ans`。\n\n该样例的 $c = 7$，它满足第 7 个测试点的限制条件。\n\n**【样例 5】**\n\n见附件中的 `wormhole5.in/ans`。\n\n该样例的 $c = 9$，它满足第 9 个测试点的限制条件。\n\n**【样例 6】**\n\n见附件中的 `wormhole6.in/ans`。\n\n该样例的 $c = 11$，它满足第 11 个测试点的限制条件。\n\n**【样例 7】**\n\n见附件中的 `wormhole7.in/ans`。\n\n该样例的 $c = 15$，它满足第 15 个测试点的限制条件。\n\n**【样例 8】**\n\n见附件中的 `wormhole8.in/ans`。\n\n该样例的 $c = 17$，它满足第 17 个测试点的限制条件。\n\n**【样例 9】**\n\n见附件中的 `wormhole9.in/ans`。\n\n该样例的 $c = 20$，它满足第 20 个测试点的限制条件。\n\n**【样例 10】**\n\n见附件中的 `wormhole10.in/ans`。\n\n该样例的 $c = 22$，它满足第 22 个测试点的限制条件。\n\n**【子任务】**\n\n对于所有测试点，\n\n- $1\\le n \\le 2\\cdot 10^3$，$0 \\le m \\le 10^3$，$1 \\le k \\le 10^{15}$；\n- $1 \\le u,v \\le n$，$1 \\le w \\le m$；\n- 保证初始建造的 $mn$ 条虫洞构成一个好的建造方案。\n\n| 测试点编号 | $n$ | $m$ | $k$ |\n| :--: | :--: | :--: | :--: |\n| $1\\sim 4$ | $\\le 5$ | $\\le 3$ |$ \\le 3$ |\n| $5\\sim 6$ | $\\le 2\\cdot 10^3$| $=0$ | $=1$|\n| $7\\sim 8$ | $\\le 10^2$ | $=1$| $=1$ |\n| $9\\sim 10$ | $\\le 10^2$ | $\\le 10$ | $=1$|\n| $11\\sim 14$ | $\\le 10^2$ | $\\le 10$ | $\\le 10^3$|\n| $15\\sim 16$ | $\\le 10^2$ | $=0$ | $\\le 10^{15}$ |\n| $17\\sim 19$ | $\\le 10^2$ | $\\le 10$ | $\\le 10^{15}$ |\n| $20\\sim 21$ | $\\le 2\\cdot 10^3$ | $\\le 10^3$ | $\\le 10^2$ |\n| $22\\sim 25$ | $\\le 2\\cdot 10^3$ | $\\le 10^3$ | $\\le 10^{15}$ |\n\n**【提示】**\n\n本题部分测试点输入规模较大，我们推荐你使用较为快速的读入方式。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10219","tags":["各省省选","2024","O2优化"],"sample_group":[["1 4 1 1\n1 2 1\n2 1 1\n3 4 1\n4 3 1","8"]],"created_at":"2026-03-03 11:09:25"}}