CF2261F2 Plegma II: Ask Me Any Cell (Hard Version)

请注意，F1 和 F2 的分数分布十分不同。本题明显比 F1 更加困难。 本题提供了可视化工具，你可以通过[这个链接](https://codeforces.com/assets/contests/2261/F_16d6cdc51811e4c62b25c3.html)进行查看。 本题禁止 Hack。 这是该问题的高难版本，唯一的区别在于 $ n $ 和 $ k $ 的范围不同。 Verity 有一个 $ n $ 行 $ n $ 列的网格，行编号为 $ 1 $ 到 $ n $（自上而下），列编号为 $ 1 $ 到 $ n $（自左而右）。第 $ p $ 行第 $ q $ 列的格子记作 $ (p, q) $。 Verity 还有一个机器人 Circuity，功能极其简单。Verity 需要编程控制机器人 Circuity，使其能够自动定位网格中的特定格子，并确保这些格子不会被其他机器人发现。 本题分为两个阶段。 阶段 1：Verity（编码） 在本阶段，Verity 需要对网格中的某一目标格子进行编码。 Verity 收到目标格子 $ (r, c) $，并且要为网格的每个格子分配一个二进制值（$0$ 或 $1$）。数值为 $1$ 的格子上会放置发射信号的信标，数值为 $0$ 的格子保持空白。 不过，Verity 认为信标太少会让外来者也能轻松定位目标格子。因此，他觉得最多只能用 $k$ 个 $0$。 阶段 2：Circuity（解码） 本阶段，Circuity 需要依据 Verity 编码后的网格来定位目标格子。但 Circuity 无法高效处理较大的网格。 在任意时刻，Circuity 怀疑目标格子位于当前由 $ (x_0, y_0) $ 和 $ (x_1, y_1) $ 构成的子矩阵内。最初，$ (x_0, y_0) = (1, 1) $，$ (x_1, y_1) = (n, n) $。 Circuity 需要连续做出恰好 $2n-2$ 次决策，每次决策如下： Circuity 可以感知到当前子矩阵中的信标数量，记为 $S$。形式上，$S$ 为由 $ (x_0, y_0) $ 和 $ (x_1, y_1) $ 所界定子矩阵内值为 $1$ 的格子数量。 仅基于 $S$，Circuity 必须从下列操作中选择一个： - 操作 U：令 $x_0$ 加 $1$。 - 操作 L：令 $y_0$ 加 $1$。 - 操作 D：令 $x_1$ 减 $1$。 - 操作 R：令 $y_1$ 减 $1$。 请注意，本次决策不可依赖以往的决策，也不可直接依赖 $x_0, x_1, y_0$ 或 $y_1$ 的值。Circuity 无记忆，每次决策时唯一的参考参数是当前的 $S$。 若任意时刻满足 $x_0 > x_1$ 或 $y_0 > y_1$，程序会异常，Circuity 任务失败。 Verity 在网格中编码的目标格子为 $ (r, c) $。在完成所有 $2n-2$ 次决策后，必须有 $x_0 = x_1 = r$ 且 $y_0 = y_1 = c$。 共有 32 组测试数据： - 每个 $n = 3, 10, 11, ..., 40$ 均各有一组测试，且顺序排列。 - 对于允许的每个 $n$，$k=f(n)$，其中 $f(n)$ 表示在 $n \times n$ 网格上编码任意目标格子时最坏情况下所需的最小 $0$ 的个数。

仅包含一个整数 $n$（$n=3$ 或 $10 \le n \le 40$）。

- **阶段 1：** 输出 $n^2$ 个二进制网格。 第 $i$ 个网格对应当目标格子为 $ (r, c) $ 时的方案，其中 $r = \lfloor \frac{i-1}{n} \rfloor + 1$，$c = ((i-1) \bmod n) + 1$。 换言之，第一个网格对应目标 $ (1,1) $，第二个网格对应 $ (1,2) $，第 $n+1$ 个网格对应目标 $ (2,1) $，依此类推。 每个网格中 $0$ 的个数最多为 $k=f(n)$。 - **阶段 2：** 输出一个长度为 $n^2+1$ 的序列：$a_0, a_1, a_2, \ldots, a_{n^2}$。每个字符为 U、D、L 或 R 之一。第 $i$ 个字符表示如果 $S=i$，那么 Circuity 采取第 $a_i$ 个操作。

以第三个网格（目标格子为 $ (1,3) $）为例。 Verity 选择如下二进制网格： ``` 110 110 110 ``` 操作序列为： ``` DURLDULRUU ``` 刚开始，Circuity 检查由 $ (1,1) $ 和 $ (3,3) $ 构成的整个子矩阵。 它需要定位到格子 $ (1,3) $，故需做 $2 \times 3 - 2 = 4$ 次决策。 - 决策 1：当前子矩阵中有 $S=6$ 个 $1$，Circuity 执行操作 $a_6=\mathtt{L}$。子矩阵更新为 $[(1,2),(3,3)]$。 - 决策 2：此时有 $S=3$ 个 $1$，执行 $a_3=\mathtt{L}$。子矩阵更新为 $[(1,3),(3,3)]$。 - 决策 3：此时 $S=0$，执行 $a_0=\mathtt{D}$。子矩阵更新为 $[(1,3),(2,3)]$。 - 决策 4：此时 $S=0$，继续执行 $a_0=\mathtt{D}$。子矩阵更新为 $[(1,3),(1,3)]$。 所有决策完成后，Circuity 成功到达目标格子 $ (1,3) $。 由 ChatGPT 5 翻译