冥王星实验室：题解

思路

先固定一个布局的最小外接矩形为 $h\times w$。因为矩形的四条边都被布局接触，任何这样的布局周长至少为 $2(h+w)$；同时必须有 $hw\ge n$。

因此只需找到最小整数 $s$，使得存在正整数 $h,w$ 满足

乘积在 $h,w$ 尽量接近时最大，所以可直接由 $k=\lfloor\sqrt n\rfloor$ 分类：

• $n=k^2$ 时 $s=2k$；
• $k^2<n\le k(k+1)$ 时 $s=2k+1$；
• $k(k+1)<n<(k+1)^2$ 时 $s=2k+2$。

最小周长就是 $2s$。

对任意满足 $h+w=s,hw\ge n$ 的有序矩形，记需要删除的格子数为 $d=hw-n$。由于 $s$ 已经最小，可以证明 $d<\min(h,w)$。要在删除格子后仍保持周长为 $2s$，删除部分必须分别从矩形的四个角向内形成四个互不相交的杨图。一个角删除 $x$ 个格子的方式数等于整数 $x$ 的分拆数。

于是，四个角一共删除 $d$ 个格子的方式数，是生成函数

中 $z^d$ 的系数，记为 $C_4(d)$。答案为

其中 $(h,w)$ 是有序对，所以旋转后的布局会被分别计数。

做法

当 $u=1$ 时，取第一个满足条件的 $h$，令 $w=s-h$，先填满整个矩形，再从左上角沿第一列删去 $hw-n$ 个格子。这正是一个角上的杨图，所得周长为 $2s$。

当 $u=2$ 时，先求所有询问可能出现的最大缺口 $D$。用完全背包计算四染色整数分拆：初始 $f_0=1$，依次处理四种角颜色；对每种颜色，再依次加入大小为 $1,2,\ldots,D$ 的部件。完成后 $f_d=C_4(d)$。

对每个询问，用二分找到最小合法高度 $L$。所有合法有序高度恰为 $L,L+1,\ldots,s-L$，逐个累加 $f_{h(s-h)-n}$。

小规模子任务可以枚举外接矩形中的所有格子子集，规范化后直接计算周长；中规模子任务可以对每个询问单独执行四染色分拆 DP；满分做法只预处理一次并供所有询问共享。

正确性证明

引理 1：任意 $n$ 格布局的周长至少为 $2s$。

设布局的最小外接矩形为 $h\times w$。其四条边都被布局接触，沿每个水平方向和竖直方向至少各产生两段外边界，因此周长至少为 $2(h+w)$。又有 $hw\ge n$，而 $s$ 是所有满足该条件的 $h+w$ 的最小值，所以周长至少为 $2s$。

引理 2：构造算法输出的布局周长恰为 $2s$。

算法从一个满足 $h+w=s$ 的实心矩形开始，并只从一个角删除长度严格小于该边的单列前缀。每删除一个角格，原来的两条外边被相邻的两条内边替代，周长不变；四条外接矩形边仍均被接触。故最终周长仍为 $2(h+w)=2s$。结合引理 1，它是最优布局。

引理 3：固定合法有序矩形 $h\times w$ 后，最优布局与总大小为 $d=hw-n$ 的四个有色整数分拆一一对应。

周长达到下界 $2(h+w)$ 时，边界不能产生额外凹凸贡献。因此空格只能从四个角开始，且同一角逐行删除长度必须单调，正好形成一个杨图；其行长构成一个整数分拆。最小性给出 $d<\min(h,w)$，所以四角区域不会相交。反之，任意四个总大小为 $d$ 的角杨图都只用外边替换内边，保持周长 $2(h+w)$。映射双向唯一，故结论成立。

定理：计数算法输出所有且仅有的最优布局数量。

由引理 1，最优布局的外接矩形必满足 $h+w=s$；由引理 3，固定有序矩形的数量为 $C_4(hw-n)$。算法遍历所有这样的有序矩形并求和，不重不漏。故输出计数正确。

复杂度

令 $D=O(\sqrt N)$ 为最大缺口，$R$ 为每个询问的合法矩形数量。预处理时间为 $O(D^2)$，空间为 $O(D)$；每个计数询问用 $O(\log N+R)$ 时间。构造模式的总输出量为 $O(\sum n)$。