#216397. [科大国创杯初中组 2026] 构造题

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

小可可需要你构造一个 个点 条边且无重边的有向无环图（节点从 开始标号），其中点 的入度和点 的出度必须为 。并且，对于 中的每一个整数 ，都能通过保留图中的一部分有向边使得从点 到点 的不同路径方案数为 。请给出你构造的有向无环图以及对于每一个 需要保留哪些边。

答案不唯一，因此你只需输出任意一种可行方案，详见输出格式。你可以自己指定 的大小，但必须保证 。

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

• 第一行输出两个正整数 表示你构造的有向无环图的点数和边数。
• 接下来 行，第 行输出两个正整数 表示图中的第 条有向边 。
• 接下来 行，第 行输出一个长度为 的仅由 构成的字符串，表示要使得点 到点 的不同路径方案数为 的情况下选择保留哪些边，从左到右第 个字符若为 表示保留第 条边， 表示不保留。

样例输入 1

3

样例输出 1

5 6
1 2
2 5
1 3
3 5
1 4
4 5
000000
110000
111100
111111

样例解释

样例中 。下页图是样例输出中构造出的一种可行的图。

当六条边全部不选的时候，显然点 无法到达点 ，方案数为 。

仅保留第 条边时，点 到点 仅有一条路径可选 ()，方案数为 。

保留第 条边时，点 到点 有两条路径可选 ( 和 )，方案数为 。

所有边全部保留时，点 到点 有三条路径可选 ( 和 )，方案数为 。

因此，这组构造方案是合法的。

数据范围

对于所有数据，保证 。

本题共计二十个测试点，每个测试点的输入是已知的（详见下表）。只有你的构造合法，并且满足 才可获得该测试点的分数，否则该测试点不得分。

温馨提示

• 本题 较大时输出量较大，因此请使用合适的方式输出。你也应当使用恰当的方法打开输出文件以防止电脑崩溃。

• 本题下发校验器 checker.cpp 供你测试你的构造是否合法。下发的校验器与最终评测中使用的校验器有所不同，你也无需关心其中的具体内容。请将本题下发文件

• checker.cpp 解压缩到你的本题程序所在文件夹中，并在你的本题程序所在文件夹中右键单击，选择菜单中的“在终端打开”，然后使用以下命令编译 checker.cpp： g++ checker.cpp -o checker -O2 -std=c++14

• 随后用以下命令测试你的输出： ./checker construct.in construct.out

• 成功运行指令后，如果你的构造合法，你将会看到 Accepted，否则你会看到 Wrong answer 以及详细错误信息。