题目来源: 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 \]
阅读全文…