2020 CCPC WannaFly 冬令营 Day5J 题解

题目来源: 2020 CCPC Wannafly 冬令营 Day5: J. Xor on Figures

题面

给定一个整数 $k$ 以及一个 $2^k\times2^k$ 矩阵 $\boldsymbol A$ , $\boldsymbol A$ 中任一元素 $a_{ij}$ 都有 $a_{ij}\in\{0,1\}$.

定义平移 $m\times n$ 矩阵 $\boldsymbol X$ 操作如下: \[ \boldsymbol X=\left[\begin{array} {cc} \boldsymbol A & \boldsymbol B\\ \boldsymbol C & \boldsymbol D \end{array} \right] :\Longrightarrow \boldsymbol X \rightarrow \left[\begin{array} {cc} \boldsymbol D & \boldsymbol C\\ \boldsymbol B & \boldsymbol A \end{array} \right] \] 其中 $\boldsymbol A$ 是 $a\times b$ 矩阵, $a\in[0,m]\cap\mathbb Z,b\in[0,n]\cap\mathbb Z$.

定义用矩阵 $\boldsymbol B$ 覆盖矩阵 $\boldsymbol A$ 操作如下: \[ \boldsymbol B(b_{ij})\sim \boldsymbol A(a_{ij}) :\Longrightarrow \boldsymbol A\rightarrow (a_{ij}\,\mathrm{xor}\,b_{ij}) \] 你可以选择任意多个经过任意平移操作后的 $\boldsymbol A$ 依次覆盖一个 $\boldsymbol{0}$ 矩阵, 求最终可以得到多少种不同的矩阵.

数据范围

\[ 1\leq k\leq5 \]

题解

定义数域 $B=\{0,1\}$ 上的加法和数量乘法运算: \[ \begin{align} \forall a, b\in B, \quad&a\oplus b =a \,\mathrm{xor}\, b\\ &a\odot b = a \cdot b \end{align} \] 考虑 $m\times n$ 的矩阵 $ A M_{mn}(B)$, 对 $\boldsymbol A(1; 1)$ 做一个标记, 则对这个矩阵进行平移操作后, 标记可能在任意一个位置, 有 $m\times n$ 种取值. 故最多有 $ m n$ 个操作算子 $\boldsymbol F$.

定义数域 $B$ 上矩阵的加法和数量乘法运算: \[ \begin{aligned} & \forall \boldsymbol X(x_{ij}), \boldsymbol Y(y_{ij})\in M_{m\times n}(B), & \boldsymbol X\oplus \boldsymbol Y&=(x_{ij}\oplus y_{ij})\\ & \forall a\in B, \boldsymbol X(x_{ij})\in M_{m\times n}(B), & a\odot \boldsymbol X&=(a\odot x_{ij}) \end{aligned} \] 这样, $ M_{mn}(B) $ 构成了数域 $B$ 上的线性空间.

显然, $\langle\boldsymbol F \rangle$ 是 $M_{m\times n}(B)$ 的一个线性子空间. 我们需要求的就是 $|\langle\boldsymbol F\rangle|$.

考虑 $\langle\boldsymbol F \rangle$ 的一个基 $\mathfrak B=\{\lambda_i;i\in[1, \mathrm{rank}\langle\boldsymbol F\rangle]\cap\mathbb Z\}$, 则 $\forall \boldsymbol X \in \langle \boldsymbol F\rangle$, $\boldsymbol X$ 可以被 $\mathfrak B$ 惟一地线性表出, 即存在唯一的一组 $k_i\in B,i\in[1, |\mathfrak B|]\cap\mathbb Z$, s.t. \[ \boldsymbol X=\sum_{i=1}^{|\mathfrak B|}k_i\lambda_i \] $\forall i\in[1,|\mathfrak B|]\cap \mathbb Z,k_i$ 一共有 $0,1$ 两个取值, 故 $\boldsymbol X$ 共有 $2^{|\mathfrak B|}$ 种不同的取值.

线性空间 $M_{m\times n}(B)$ 与 $B^{m\times n}$ 同构. 将所有的 $m\times n$ 个 $\boldsymbol F$ 转化成 $m\times n$ 个 $m\times n$ 维向量, 放入矩阵中高斯消元求秩即可. 复杂度为 $O(m^3n^3)=O(2^{6k})$. 位运算与高斯消元的常数极小, 可以接受.

算出矩阵的秩后, 答案即 \[ 2^{|\mathfrak B|}=2^{\mathrm{rank}\langle\boldsymbol F\rangle} \] 在 $\bmod p$ 意义下进行快速幂即可.