$4280$. 「KTSC $2021$ R1」翻牌游戏

传统 $1000$ ms $1024$ MiB $2021$ KTSC $3$ 通过 $8$ 提交

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

C++（标准为 C++ $17$ 及以上） 请在提交源代码前添加 #include "card.h"。

题目描述

题目译自 $2021$년도 국제정보올림피아드 대표학생 선발고사 - $1$차 선발고사 T$1$ 「카드 뒤집기 게임」

翻牌游戏是一种单人卡牌游戏，使用两种类型的卡牌 $A$ 和 $B$。卡牌 $A$ 上写有游戏规则的信息，具体来说，如图 $1$ 所示，包含两个整数 $N$ 和 $M$ ($M \leq N$)，以及一个 $N \times N$ 的由字符 $\texttt{O}$ 和 $\texttt{X}$ 组成的图案 $P$。

图 $1$

卡牌 $B$ 的正面是字符 $\texttt{O}$，背面是字符 $\texttt{X}$。卡牌 $B$ 用来表示卡牌 $A$ 上图案中的每个字符，为此准备了足够多的卡牌 $B$。

游戏开始时，选择一张卡牌 $A$，并根据卡牌上的 $N$ 值，将卡牌 $B$ 按 $N \times N$ 的格子排列。初始时，所有卡牌 $B$ 都显示 $\texttt{X}$。每张卡牌的位置如图 $2$ 所示，用行号和列号区分。

图 $2$

初始排列完成后，玩家可以根据需要重复进行翻牌操作。一次翻牌操作分为两个步骤：

步骤 $1$：在 $N \times N$ 的格子中选择任意一行或一列，并根据卡牌 $A$ 上的整数 $M$ 选择一个整数 $k$ ($0 \leq k < M$)。

步骤 $2$：如果选择的是第 $i$ 行，则对所有满足 $j \equiv k \pmod{M}$ 的列 $j$ 进行翻牌操作，即翻转 $(i, j)$ 位置上的所有卡牌。同样地，如果选择的是第 $j$ 列，则对所有满足 $i \equiv k \pmod{M}$ 的行 $i$ 进行翻牌操作，即翻转 $(i, j)$ 位置上的所有卡牌。

玩家需要通过重复翻牌操作，使格子中的卡牌图案与卡牌 $A$ 上的图案 $P$ 一致。我们来判断一下，这是否真的可行。

实现细节

你需要实现以下函数：

bool reversal(int N, int M, vector<string> P);

• 该函数只会被调用一次。
• 参数 $N$ 表示格子的大小。
• 参数 $M$ 表示翻牌操作中翻转卡牌的间隔。
• 参数 $P$ 是一个包含 $N$ 个字符串的数组，每个字符串长度为 $N$，表示需要形成的图案的第 $i$ 行。
• 该函数返回一个布尔值，如果可以通过翻牌操作从初始排列形成图案 $P$，则返回 true，否则返回 false。

注意：提交的代码中不应包含任何输入输出操作。

样例

考虑 $N=5$, $M=2$，图案 $P=[\texttt{XXXOX}, \texttt{XXXOX}, \texttt{OOOXO}, \texttt{XOXXX}, \texttt{XOXXX}]$ 的情况。评测程序将调用如下函数：

reversal(5, 2, ["XXXOX", "XXXOX", "OOOXO", "XOXXX", "XOXXX"]);

下图展示了从初始状态开始，通过翻牌操作，根据选择的行/列号和 $k$ 值，卡牌图案的变化过程。最终形成了图案 $P$。因此，调用的 reversal 函数应返回 true。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq M \leq N \leq 1000$
• $P$ 中的所有字符都是 $\texttt{O}$ 或 $\texttt{X}$

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$11$	$N \times M \leq 10$
$2$	$50$	$M=1$
$3$	$39$	无附加限制

示例评测程序

示例评测程序的输入格式如下：

• 第 $1$ 行：$N$ $M$
• 第 $2+i$ 行：$P[i]$

示例评测程序可能与实际评测程序不同。