P16344 [科大国创杯初中组 2026] 构造题

Subtask 0 为民间数据，Subtask 1 为官方测试数据。

小可可需要你构造一个 $n$ 个点 $m$ 条边且**无重边**的有向无环图（节点从 $1$ 开始标号），其中点 $1$ 的入度和点 $n$ 的出度必须为 $0$。并且，对于 $0 \sim p$ 中的每一个整数 $i$，都能通过保留图中的一部分有向边使得从点 $1$ 到点 $n$ 的不同路径方案数为 $i$。请给出你构造的有向无环图以及对于每一个 $i$ 需要保留哪些边。 答案不唯一，因此你只需输出任意一种可行方案，详见输出格式。你可以自己指定 $n, m$ 的大小，但必须保证 $n \le 24, m \le 65$。 > 一条经过 $|P|$ 个点的，从点 $1$ 到点 $n$ 的路径 $P$ 可以描述为一个长度为 $|P|$ 的序列 $(P_1, P_2, \dots, P_{|P|})$，其中 $P_1 = 1, P_{|P|} = n$，并且对于 $i = 1, 2, \dots, |P| - 1$，图中都存在 $P_i \to P_{i+1}$ 的有向边。 > 两条路径 $A, B$ 不同，当且仅当 $|A| \ne |B|$，或者存在一个 $1 \sim |A|$ 中的正整数 $i$，使得 $A_i \ne B_i$。

输入仅有一行一个正整数 $p$。

- 第一行输出两个正整数 $n, m$ 表示你构造的有向无环图的点数和边数。 - 接下来 $m$ 行，第 $i$ 行输出两个正整数 $u, v$ 表示图中的第 $i$ 条有向边 $u \to v$。 - 接下来 $p+1$ 行，第 $i$ 行输出一个长度为 $m$ 的仅由 $01$ 构成的字符串，表示要使得点 $1$ 到点 $n$ 的不同路径方案数为 $i-1$ 的情况下选择保留哪些边，从左到右第 $j$ 个字符若为 $1$ 表示保留第 $j$ 条边，$0$ 表示不保留。

#### ****样例解释**** 样例中 $p=3$。下页图是样例输出中构造出的一种可行的图。  当六条边全部不选的时候，显然点 $1$ 无法到达点 $5$，方案数为 $0$。 仅保留第 $1, 2$ 条边时，点 $1$ 到点 $5$ 仅有一条路径可选 ($1 \to 2 \to 5$)，方案数为 $1$。 保留第 $1, 2, 3, 4$ 条边时，点 $1$ 到点 $5$ 有两条路径可选 ($1 \to 2 \to 5$ 和 $1 \to 3 \to 5$)，方案数为 $2$。 所有边全部保留时，点 $1$ 到点 $5$ 有三条路径可选 ($1 \to 2 \to 5, 1 \to 3 \to 5$ 和 $1 \to 4 \to 5$)，方案数为 $3$。 因此，这组构造方案是合法的。 #### ****数据范围**** 对于所有数据，保证 $p \le 75000$。 本题共计二十个测试点，每个测试点的输入是已知的（详见下表）。只有你的构造合法，并且满足 $n \le 24, m \le 65$ 才可获得该测试点的分数，否则该测试点不得分。 | 测试点编号 | $p=$ | 测试点编号 | $p=$ | 测试点编号 | $p=$ | 测试点编号 | $p=$ | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | $1$ | $5$ | $6$ | $300$ | $11$ | $6000$ | $16$ | $35000$ | | $2$ | $10$ | $7$ | $600$ | $12$ | $8000$ | $17$ | $45000$ | | $3$ | $20$ | $8$ | $1000$ | $13$ | $10000$ | $18$ | $55000$ | | $4$ | $50$ | $9$ | $2000$ | $14$ | $15000$ | $19$ | $65000$ | | $5$ | $100$ | $10$ | $4000$ | $15$ | $25000$ | $20$ | $75000$ | #### ****温馨提示**** - 本题 $p$ 较大时输出量较大，因此请使用合适的方式输出。你也应当使用恰当的方法打开输出文件以防止电脑崩溃。 - 本题下发校验器 `checker.cpp` 供你测试你的构造是否合法。下发的校验器与最终评测中使用的校验器有所不同，你也无需关心其中的具体内容。请将本题下发文件 - `checker.cpp` 解压缩到你的本题程序所在文件夹中，并在你的本题程序所在文件夹中右键单击，选择菜单中的“在终端打开”，然后使用以下命令编译 `checker.cpp`： `g++ checker.cpp -o checker -O2 -std=c++14` - 随后用以下命令测试你的输出： `./checker construct.in construct.out` - 成功运行指令后，如果你的构造合法，你将会看到 `Accepted`，否则你会看到 `Wrong answer` 以及详细错误信息。