[题解] 时隔一年,再谈 Elegant Square

· · 算法·理论

前言

人类玩的太差了。

本文为 Elegant Square - Problem - QOJ.ac 的数据范围下最优构造题解。

正文

我们之前在 [笔记] 关于正交拉丁方的构造与应用 - 沉石鱼惊旋 的博客 里写到:本题使用一对正交拉丁方的构造,一组填质数一组填 Square-Free 的数,就能做到一个很优的解。在本题 n=30 时,最大元素只有 8878。

但是这不是最优的解。甚至我们可以找到一个疑似下界的值,搭配一些强力搜索,可以构造得到下界。总之,结论是本题在 3\leq n\leq 30 时最优解分别为:21,65,102,154,231,319,403,518,629,731,893,1085,1222,1403,1742,1943,2130,2263,2553,2686,3034,3293,3619,3910,4141,4494,4674,5014。

提交记录在:Submission #3475822 - QOJ.ac。代码有 55kb,因为直接把表写进去了。浏览器有加载不出的风险,谨慎观看。代码可直接在 ElegantSquare.cpp 下载。

甚至因为不存在一对 n=6 的正交拉丁方,所以我们的 n=6 之前还是手动构造的,不妨就从这个 case 开始分析一下下界。我们先声称下界有 L(6)=154,接下来证明 153 不可行。

我们先只保留在 [1,153] 中 Square-Free 的数。然后对于一个质数 p,若其的倍数在目前剩余集合中,少于 n=6 个,则将 p 的所有倍数删除。重复这个过程,我们可以得到这样一个大小为 42 的集合:

C^*=\left\{ \begin{gathered} 1,2,3,5,6,7,10,11,13,14,15,17,19,21,\\ 22,26,30,33,34,35,38,39,42,51,55,57,65,66,\\ 70,77,78,85,91,95,102,105,110,114,119,130,133,143 \end{gathered} \right\}

我们先讨论集合 P=\{2,7\}。2,7 的倍数分别有 17,11 个,重合 3 个。发现在 C^* 中删除 2,7 的倍数后,只剩了 H_0=42-17-11+3=17 个数。但是 2 的倍数与 7 的倍数选择的数量,必须是 n=6 的倍数。而 H_0+12+6=35\lt n^2=36,因此无解。且我们确实能构造一个最大元素为 154 的解:

\begin{bmatrix} 17 & 130 & 19 & 21 & 70 & 33\\ 105 & 34 & 35 & 38 & 11 & 39\\ 114 & 77 & 51 & 5 & 65 & 14\\ 91 & 57 & 154 & 85 & 3 & 10\\ 55 & 7 & 13 & 42 & 102 & 95\\ 2 & 15 & 30 & 143 & 133 & 119\\ \end{bmatrix}

继续拓展这一做法。

删除倍数少于 n 个的质数 p 及其倍数,得到一个合法候选集 C^* 这是简单的。设 C_p=\#\{x\in C^* : p\mid x\},最后选出来填入方阵的数集合为 S。T_p\leq C_p 且 n\mid T_p 表示 \#\{x\in S: p\mid x\}。我们可以得到:T_p\leq U_p=n\times \lfloor\frac{C_p}{n}\rfloor。例如 n=6 时虽然有 17 个偶数在 C^* 中,但是 U_p=12 因为选择的数量必须是 n 的倍数。

这里 GPT 神力给了个很不是人的做法:

我们为每个 p 钦定一个 w_p\geq 0 并选择正整数 t,定义 d(v)=\sum\limits_{p\mid v}w_p,h(v)=\max\{0,t-d(v)\},计算 A=\sum\limits_p w_p U_p,B=\sum\limits_{v\in C^*}h(v)。

我们声称如果最大元素不超过 M 的合法方阵存在,则必有 tn^2\le A+B。因此,如果给出一组 w_p 和 t,使得 A+B<tn^2,就证明了这样的方阵不存在,M 不可行。

证明考虑对任意 v,有 t\le d(v)+h(v),对所有数求和得到:

\begin{aligned} tn^2 &\leq\sum_{v\in S}d(v)+\sum_{v\in S}h(v)\\ &=\sum_p w_p T_p+\sum_{v\in S}h(v)\\ &\leq\sum_p w_p U_p+\sum_{v\in C^*}h(v)\\ &=A+B \end{aligned}

实际上对于 n\leq 30,我们有一个很干净的做法。取素数集合 P,\forall p,w_p=[p\in P]。那么 d(v)=\#\{p\in P:p\mid v\}。设 H_j=\#\{v\in C^*:d(v)=j\}。

取 t=1 时,即需要满足 n^2\leq\sum\limits_{p\in P}U_p+H_0。

它的直接含义是,选中的数中,含 P 中某个素数的数字个数至多为 \sum_{p\in P}U_p,完全不含 P 中素数的数字至多有 H_0 个。

取 $t=2$ 时,即需要满足 $2n^2\le\sum_{p\in P}U_p+2H_0+H_1$。类似的我们也都能找到这样的 $P$ 不满足限制。 具体一点,找出这样的 $P$ 的过程,可以先使用之前正交拉丁方的构造把上界找出来,压小需要判断的范围。在范围内最终还留在 $C^*$ 内的质数不多。然后对集合大小不超过 $2$ 的枚举一遍,还有一段后缀集合 $P=\{p:p\ge q\}$ 等先做一遍。 并且考虑 $a_p=\#\{v\in C^*:p\mid v,\ d_P(v)<t\},d_P(v)=\#\{q\in P:q\mid v\},E(P)=\sum_{q\in P}U_q+ \sum_{v\in C^*}\max\{0,t-d_P(v)\}$ 则 $E(P\cup\{p\})-E(P)=U_p-a_p$,选择 $a_p\gt U_p$ 的进行改进,删除同理。其实事实上没有人知道可以取 $w_p\in\{0,1\}$ 所以一开始代码还有调整 $w_p$ 的部分。 此时已经证明了下界,还需要构造达到该下界的方阵,才能确定最优值。 构造时先将上限设为 $M=L(n)$,并重新生成候选集 $C^*$。 先解一个 $|C^*|+|\mathcal P|$ 个变量的整数规划,其中 $\mathcal P$ 是 $C^*$ 中所有素数组成的集合: $$ \begin{aligned} x_v&\in\{0,1\},\qquad k_p\in\mathbb Z_{\ge0},\\ \sum_{v\in C^*}x_v&=n^2,\\ \sum_{\substack{v\in C^*\\p\mid v}}x_v &=nk_p\qquad(p\in\mathcal P). \end{aligned} $$ 整数规划跑完后,每种素数总共出现 $nk_p$ 次。接下来要将它们分成 $n$ 组,每组 $n$ 个数,每种素数出现 $k_p$ 次。 假设当前集合对应 $m$ 行,令 $a=\lfloor\frac{m}{2}\rfloor$,用一个整数规划选出子集,要求选 $an$ 个数出来,其中含 $p$ 的有 $ak_p$ 个。这样选出的部分对应 $a$ 行,剩余部分对应 $m-a$ 行。继续递归,直到每组对应一行。若某一步整数规划无解,则回退或重新选择前面的解。 此时,每行乘积都已经等于 $\prod_p p^{k_p}$,但各列仍可能不平衡。 记 $e_{c,p}=\#\{r:p\mid a_{r,c}\}-k_p$ 并定义错误量 $E=\sum\limits_{c,p}e_{c,p}^2$。当 $E=0$ 时,所有列也正确了。交换同一行两列 $c,d$ 的数字时,若两数对 $p$ 的整除标记之差为 $\delta=[p\mid a_{r,c}]-[p\mid a_{r,d}]$,则 $\Delta E_p=2\delta(e_{d,p}-e_{c,p})+2\delta^2$。并且对于 $k_p=1$ 的素数还可以提前跑二分图匹配安排位置。 但是这个也不一定搜得出来,可能很多列都对了就一些不对,然后卡死了。这时选一个自由素数集合 $S$,包含出错的素数,再尝试加入辅助素数。例如 $29$ 的列上不对,我们就取 $S=\{19,29\}$。 那么原来每一格 $a_{r,c}$,有 $g_{r,c}=\frac{a_{r,c}}{19^{[19\mid a_{r,c}]}29^{[29\mid a_{r,c}]}}$,重新构造的时候就可以选择 $\{g_{r,c},19g_{r,c},29g_{r,c},551g_{r,c}\}$ 中不超过 $M$ 的数。限制就是在保证每行每列改完后 $p$ 在每行每列出现 $k_p$ 次的情况下,再要求 $g_{r,c}$ 一样的格子不能选出来同一个数。使用已有工具解一个这样的 SAT 问题即可。 通过这些优化,最终也是成功构造出了 $3\leq n\leq 30$ 的所有最优解,可喜可贺。 # 拟合 EricWan 问这个能不能拟合 $n-L(n)$。 可以的兄弟,可以的。$L(n)=n^{2+o(1)},\lim\limits_{n\to +\infty} \frac{\ln(L(n))}{\ln n}=2$。 具体的目前可以给出: $$ \left(\dfrac{\pi^2}{6(1-\ln 2)}-o(1)\right)n^2\leq L(n)\leq \left(\dfrac{\pi^2}{6}+o(1)\right)n^2\ln n $$ 两个常数分别为 $5.36066,1.64493$。这个不一定是最紧的,或许最紧的界还有待讨论,不过也足以确定其多项式增长指数为 $2$。 上界是这么来的:用之前的正交拉丁方构造,取最小的 $n$ 个 Square-Free 数,最大值为 $A=\left(\frac{\pi^2}{6}+o(1)\right)n$。再取大于 $A$ 的前 $n$ 个素数,最大值为 $B=(1+o(1))n\ln n$,全乘起来按照一对正交拉丁方填进去即可。所以有 $L(n)\leq AB =\left(\frac{\pi^2}{6}+o(1)\right)n^2\ln n$。 而下界这么来的: 取一个达到最优值的方阵,令其最大元素为 $M=L(n)$。任何被使用的素数 $p$,都得满足 $p\leq M/n$。 又有 $M\geq n^2$,故 $M/n\ge\sqrt M$。一个不超过 $M$ 的数,至多包含一个大于 $M/n$ 的质因子。 令 $Q(x)$ 表示不超过 $x$ 的平方自由数个数。删除这些大素数的倍数后,候选数的数量恰为 $N(M,n)=Q(M)-\sum\limits_{M/n\lt p\leq M}Q(M/p)

而 Q(x)=\frac{6}{\pi^2}x+O(\sqrt x),\sum\limits_{p\leq x}\frac{1}{p}=\ln\ln x+C_0+o(1),由于 M\geq n^2,加上前面的上界所以保证了 \ln M= (2+o(1))\ln n,所以

\sum\limits_{M/n<p\le M}\frac1p = \ln\frac{\ln M}{\ln(M/n)}+o(1) =\ln2+o(1)

带入 N(M,n) 可以得到 N(M,n)=\left(\frac6{\pi^2}(1-\ln2)+o(1)\right)M。而因为至少需要 n^2 个不同元素所以 N(M,n)\geq n^2 所以

M\geq \left(\frac{\pi^2}{6(1-\ln2)}-o(1)\right)n^2 =(5.36066-o(1))n^2

至于为什么可以得到 N(M,n)=\left(\frac6{\pi^2}(1-\ln2)+o(1)\right)M 是因为带入后 Q 的误差之和是 o(M) 的。

令 \delta=6/\pi^2,可以把 Q(x) 写作 \delta x+r(x) 其中 |r(x)|\leq C_1\sqrt x,带入可以得到 N(M,n)=\delta M\left(1-\sum_{M/n\lt p\leq M}\frac1p\right)+R,其中总误差 R=r(M)-\sum_{M/n\lt p\leq M}r(M/p),因此有 |R| \leq C_1\sqrt M+C_1\sum_{p\leq M}\sqrt{\frac Mp}。

这个东西可以利用 \pi(t)=O(t/\ln t) 求和得到:

\sum_{p\leq M}\frac{1}{\sqrt p}=\frac{\pi(M)}{\sqrt M}+\frac{1}{2}\int_2^M\frac{\pi(t)}{t^{3/2}}\,\mathrm{d}t=O\left(\frac{\sqrt M}{\ln M}\right)

所以 |R|=\mathcal O(\frac{M}{\ln M})=o(M)。

附录

A

A.1 n=3,下界 L=21

A.2 n=4,下界 L=65

A.3 n=5,下界 L=102

A.4 n=6,下界 L=154

A.5 n=7,下界 L=231

A.6 n=8,下界 L=319

A.7 n=9,下界 L=403

A.8 n=10,下界 L=518

A.9 n=11,下界 L=629

A.10 n=12,下界 L=731

A.11 n=13,下界 L=893

A.12 n=14,下界 L=1085

A.13 n=15,下界 L=1222

A.14 n=16,下界 L=1403

A.15 n=17,下界 L=1742

A.16 n=18,下界 L=1943

A.17 n=19,下界 L=2130

原始证书保存 t=2、非零权重 2,其不等式为 722\le720。本段将两端同时除以 2。

A.18 n=20,下界 L=2263

原始证书保存 t=2、非零权重 2,其不等式为 800\le798。本段将两端同时除以 2。

A.19 n=21,下界 L=2553

A.20 n=22,下界 L=2686

A.21 n=23,下界 L=3034

A.22 n=24,下界 L=3293

A.23 n=25,下界 L=3619

A.24 n=26,下界 L=3910

A.25 n=27,下界 L=4141

A.26 n=28,下界 L=4494

A.27 n=29,下界 L=4674

A.28 n=30,下界 L=5014