#PQJ3342x17203. QOJ 3342_17203
QOJ 3342_17203
第一试谜题II(puzzle) IOI2026 中国国家队选拔 谜题II(puzzle) 【题目描述】 厌倦了计算一些稀奇古怪的问题的答案对998244353 或109 + 7 取模后的结果,小 E 设计了一道与2 相关的谜题: 给定一个2 行2k 列的网格,你需要将1 ∼2k+1 不重不漏地填入网格的2k+1 个格 子中,并使得相邻格子之间的大小关系满足下列限制。 具体地,给定三个长度分别为2k −1, 2k, 2k −1 的01 序列a, b, c。称一个2 × 2k 的 矩阵A 为该谜题的一组解,当且仅当其同时满足以下四条约束:
- A 包含1, 2, . . . , 2k+1 中的每个整数.恰.好.一.次;
- 对于所有1 ≤i < 2k,均有ai = [A1,i < A1,i+1];
- 对于所有1 ≤i ≤2k,均有bi = [A1,i < A2,i];
- 对于所有1 ≤i < 2k,均有ci = [A2,i < A2,i+1]。 其中[P] 当条件P 成立时取值为1,否则为0。 对你而言,仅仅找出任意一组解或判断无解太过简单。既然是关于2 的谜题,小E 要求你计算谜题的解的数量对2 取模后的结果。 小E 准备了t 道网格大小相同的谜题,并使用高效的压缩手段将它们压缩在一起。 你需要对于其中每一道谜题,求出解的数量对2 取模后的结果。 【实现细节】 .选.手.不.需.要,.也.不.应.该.实.现main .函.数。 选手需要确保提交的程序包含头文件puzzle.h,即在程序开头加入以下代码: #include "puzzle.h" 1 选手需要在提交的程序源文件中实现以下函数: unsigned puzzle(int t, int k, std::vector a, 1 std::vector b, std::vector c); • t, k 分别表示谜题的个数与网格的大小。 • 对于0 ≤i < 2k −1, ai .二.进.制.下.的.第j (0 ≤j < t) .位表示第j + 1 个谜题中 A1,i+1 与A1,i+2 的大小关系的限制。 • 对于0 ≤i < 2k, bi .二.进.制.下.的.第j (0 ≤j < t) .位表示第j + 1 个谜题中A1,i+1 与A2,i+1 的大小关系的限制。 • 对于0 ≤i < 2k −1, ci .二.进.制.下.的.第j (0 ≤j < t) .位表示第j + 1 个谜题中 A2,i+1 与A2,i+2 的大小关系的限制。 • 该函数需要返回一个非负整数,其中.二.进.制.下.的.第j (0 ≤j < t) .位表示第j + 1 个谜题中解的数量对2 取模后的结果。 第11 页 共14 页 第一试谜题II(puzzle) IOI2026 中国国家队选拔 • 对于每个测试点,该函数会被交互库调用.恰.好.一.次。 .注.意:.在.任.何.情.况.下,.交.互.库.运.行.所.需.时.间.均.不.会.超.过0.1 .秒,.所.用.内.存.为.固.定.大 .小,.且.均.不.超.过64 MiB。 【测试程序方式】 .试.题.目.录.下.的grader.cpp .是.交.互.库.参.考.实.现,.最.终.测.试.时.所.用.的.交.互.库.实.现.与.该 .参.考.实.现.有.所.不.同,.因.此.选.手.的.解.法.不.应.该.依.赖.交.互.库.实.现。 选手可以在本题目录下使用如下命令编译得到可执行程序: g++ grader.cpp puzzle.cpp ‐o puzzle ‐O2 ‐std=c++14 ‐static 1 对于编译得到的可执行程序: • 可执行文件将从.标.准.输.入读入以下格式的数据: – 输入的第一行包含两个正整数t, k,分别表示谜题的数量与网格的大小。 – 输入的第3i−1 (1 ≤i ≤t) 行包含一个长度为2k−1 的01 字符串a1 . . . a2k−1。 – 输入的第3i (1 ≤i ≤t) 行包含一个长度为2k 的01 字符串b1 . . . b2k。 – 输入的第3i+1 (1 ≤i ≤t) 行包含一个长度为2k−1 的01 字符串c1 . . . c2k−1。 • 可执行文件将输出以下格式的数据至.标.准.输.出: – 输出共t 行,其中第i (1 ≤i ≤t) 行包含一个非负整数,表示第i 道谜题的 解的数量对2 取模后的结果。 【样例1 输入】 2 1 1 1 2 01 3 1 4 1 5 00 6 1 7 【样例1 输出】 1 1 0 2 第12 页 共14 页 第一试谜题II(puzzle) IOI2026 中国国家队选拔 【样例2 输入】 4 2 1 100 2 1111 3 100 4 100 5 0000 6 110 7 110 8 1111 9 011 10 010 11 0000 12 010 13 【样例2 输出】 1 1 1 2 0 3 0 4 【附加文件说明】 在附加文件中:
- grader.cpp 是提供的交互库参考实现。
- puzzle.h 是头文件,选手不用关心具体内容。
- template_puzzle.cpp 是提供的示例代码,选手可参考并实现自己的代码。 【子任务】 对于所有测试数据,均有: • 1 ≤t ≤32,1 ≤k ≤18; • 对于所有1 ≤i < 2k,均有ai ∈{0, 1}; • 对于所有1 ≤i ≤2k,均有bi ∈{0, 1}; • 对于所有1 ≤i < 2k,均有ci ∈{0, 1}。 第13 页 共14 页 第一试谜题II(puzzle) IOI2026 中国国家队选拔 子任务编号 分值 特殊性质 k ≤ 1 2 2 3 无 3 5 6 4 8 5 10 A 6 25 13 无 7 5 14 A 8 20 17 B 9 10 18 无 10 15 特殊性质A:t ≤4。 特殊性质B:对于所有1 ≤i < 2k,均有bi̸ = bi+1。 【评分方式】 .注.意: • 选手不应当通过非法方式获取交互库的内部信息,如直接与标准输入、输出流进 行交互。此类行为将被视为作弊; .最.终.的.评.测.交.互.库.与.样.例.交.互.库.的.实.现.不.同。 • .本.题.首.先.会.受.到.和.传.统.题.相.同.的.限.制,例如编译错误会导致整道题目得0 分,运行 时错误、超过时间限制、超过空间限制等会导致相应测试点得0 分等。选手只能在程序 中访问自己定义的变量以及交互库给出的变量,尝试访问其他地址空间将可能导致编译 错误或运行错误。 在上述条件基础上: • 对于每个测试点,程序得到满分当且仅当调用puzzle 函数时返回的答案正确。 第14 页 共14 页