题面

给定一个整数 \(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\) 意义下进行快速幂即可.