SP21171 TAP2014D - Fractal domino

你是否曾想过这样一个问题：给定一个 **N × N** 的棋盘，用多米诺骨牌将其完全覆盖有多少种不同的方法？要求这些骨牌不能重叠，也不能留有空白的格子。多米诺骨牌由两个相邻的方格组成，既可以是水平的（即 **1 × 2** 的矩形），也可以是垂直的（即 **2 × 1** 的矩形）。例如，一个 **2 × 2** 的棋盘只有两种覆盖方式，而一个 **8 × 8** 的棋盘则有惊人的 **12,988,816** 种。 同时，如果有些方格被事先占用，我们需要计算只覆盖未被占用区域的非重叠多米诺骨牌的数量。比如，在一个中心格子被占用的 **3 × 3** 棋盘上，有两种覆盖方式，然而在 **7 × 7** 的棋盘上有 **75,272** 种。 本题在问题的基础上增加了一层复杂性。我们考虑用一种称为分形多米诺的方式进行覆盖。这种多米诺是递归的：当 **K = 0** 时，分形多米诺就是普通的多米诺；但当 **K > 0** 时，分形多米诺则由次一级的分形多米诺构成，且每个小单元都是一个 **N × N** 的棋盘。 任务要求计算当使用 **K** 级分形多米诺覆盖棋盘的所有可能方式等概率时，预计有多少比例的多米诺为垂直放置。结果要求精确到小数点后 **5** 位。

第一行是整数 **T**，表示测试用例的数量。接下来是 **T** 个测试用例。 对每个测试用例： - 第一行有两个整数 **N** 和 **K**，分别表示棋盘的大小和想要使用的分形多米诺的阶数。 - 接下来的 **N** 行代表棋盘状态，每行包含 **N** 个数；如果某个单元格被占用，则其值为 **1**，否则为 **0**。 请注意，每个棋盘都至少有一个可覆盖的方案。

对于每个测试用例，输出一行，包含一个有理数，表示按给定条件覆盖棋盘时垂直多米诺所占的比例。结果精确到小数点后 **5** 位，必要时请四舍五入。

- $1 \le T \le 100$ - $2 \le N \le 100$ - $0 \le K \le 10$ **本翻译由 AI 自动生成**