关于正交拉丁方的构造与应用

沉石鱼惊旋 · 2025-10-24 19:10:29 · 算法·理论

本文同步发表于 [笔记] 关于正交拉丁方的构造与应用 - 沉石鱼惊旋 的博客。

定义

拉丁方阵（英语：Latin square）是一种 n \times n 的方阵，在这种 n \times n 的方阵里，恰有 n 种不同的元素，每一种不同的元素在同一行或同一列里只出现一次。以下是两个拉丁方阵举例：

拉丁方阵有此名称是因为瑞士数学家和物理学家欧拉使用拉丁字母来做为拉丁方阵里的元素的符号。

设有两个阶数相同的拉丁方阵 {\displaystyle A_{1}=(a_{i,j}^{(1)})_{n\times n},A_{2}=(a_{i,j}^{(2)})_{n\times n}}，其中将所有放置位置相同的元素组成一个二元组，组合成一个新的矩阵 {\displaystyle ((a_{i,j}^{(1)},a_{i,j}^{(2)}))_{n\times n}}。 当这个新的矩阵 {\displaystyle ((a_{i,j}^{(1)},a_{i,j}^{(2)}))_{n\times n}} 中每一个元素互不相同时，拉丁方阵 {\displaystyle A_{1}} 和 {\displaystyle A_{2}} 是互相正交的。 此时，{\displaystyle A_{1}} 和 {\displaystyle A_{2}} 即为一对正交拉丁方。 而在阶数固定的情况下，所有两两正交的拉丁方所成的集合称为正交拉丁方族。

摘自于 WikiPedia 的『拉丁方阵』词条。

朝花夕拾

对于 n 为奇数和 n\equiv 0\pmod 4 的情况，构造是较为容易的。欧拉猜想，对于 n\equiv 2\pmod 4 的情况，不存在一对正交拉丁方。

然而在 1959 年，On the falsity of Euler's conjecture about the non-existence of two orthogonal Latin squares of order 4t + 2 这篇文章推翻了这一猜想。

前言

我在 20251021 打模拟赛时，做到了这样一个题：Elegant Square - Problem - QOJ.ac。而模拟赛版本要求做到 3\leq n\leq 202，且构造的最大值不超过 2\times 10^7。

我做了一整场，22 分遗憾离场。赛后发现改了几个字节就 50 分了。

这不重要，重要的是，Leo_lele 指出，这个问题的本质是构造正交拉丁方。而且，有了一组正交拉丁方之后，我们可以很轻松的做到这个问题的下界（？）。具体的，第一个矩形填前 n 个 Square-Free 的数，第二个矩形填在第一个矩形的基础上，再填若干个质数。然后把两个矩形对应位乘起来即可。

那么现在问题是如何构造一对正交拉丁方，我们查阅了许多资料，问了无数个 AI，都没有获得现成的构造代码。且碍于语言不通，我们阅读英语论文较为吃力，这个问题迟迟没有进展。

鉴于我俩做不出来这个问题，于是 yyc 把它挂到了知乎上：怎样构造 2p（4t+2）形式的正交拉丁方对？ - 知乎。同时 yyc 在精英培训群里提问，被杜老师看到了，杜老师指出了有了正交拉丁方 E - Cross Sum Construction 则这个题也可以轻松通过。

我邀请了较为熟悉的 MatrixGroup 老师。矩阵群老师连夜阅读论文，当晚便阅读了 Combinatorial Designs and Tournaments 并写下了知乎回答并同步发表在了知乎专栏与洛谷专栏。

• 正交拉丁方的构造 - 知乎
• 正交拉丁方的构造 - 洛谷专栏

第二天起床之后我便阅读了文章。在持续骚扰 ChatGPT、矩阵群和 yyc 一天之后，我成功写出了 43kb 的代码，通过了 1\leq n\leq 1000 的正交测试。

具体代码在 chenyuxuan2009/OrthogonalLatinSquare 可以阅读。作为竞赛选手我已经尽力把代码写的工程风格让它可读一点了 qwq。在此需要再次感谢 ChatGPT 为我提供了有限域乘法模板，以及找出了 4 阶有限射影平面和 5 阶有限仿射平面，以及矩阵群老师多次指出我的代码的弱智错误。

在 OI 中的使用

接下来，我会举两个题目的例子。

QOJ12905

应该是爆了目前网上所有代码的标，包括 pp_orange 留下来的圣遗物 std。

首先有一些很自然的想法：我们找到两个矩阵，每个矩阵填一些质数，且一个质数在每行和每列都出现了一次，然后把他和前一个矩阵乘起来。如果找不到，我们再加一个矩形。事实上，网络上此题几乎所有题解都是这么做的，即使不是也需要引入 \mathcal O(1) 个额外的质数。

不难发现这个就是在找一对正交拉丁方。而我们根据前人的智慧，除了 n=2,6 都是有构造的。

有了正交拉丁方，直接就找出来了。但是，我们真的需要两个质数吗？稍微想一下可以发现，我们第一个矩阵可以填若干个 Square-Free 的数。第二个矩阵再填一些质数。

依此，我们在 n=202 的时候，最大值只有 566209。而 n=30 的时候，只有 8878。

Submission #1574614 - QOJ.ac

AGC064E

需要参考一些原题解 Editorial - AtCoder Grand Contest 064 和洛谷目前唯一一篇题解 AT_agc064_e [AGC064E] Cross Sum Construction题解 - 洛谷专栏。

总之，对于 n=2,6，这个数据范围非常小，足以搜索出一个方案通过本题。

对于其他情况，我们已有两个拉丁方 L^1,L^2，则 s_{i,j}\gets a_{L^1_{i,j}}+b_{L^2_{i,j}} 即可。不需要去精心讨论，这些工作我们构造拉丁方的时候就已经做过了。

Submission #70385883 - AtCoder Grand Contest 064

代码的 n=2,6 并非搜索，贺了一下题解，抱歉。

另外杜老师指出这个题写个搜子能过 1000。

后话

OLS 相关内容，我研究了半周。本周二打完模拟赛我做了半天的 OLS 相关内容，读了一晚上的论文，却没有太大收获。本以为这是浪费时间，作为高一正式选手我可能把时间浪费在这上面是很愚蠢的，有这个时间我的同届对手们已经卷了十个题了（

但是在一步步讨论、挖掘、请教中，做这种“科研”也是有他的独特魅力的。前人智慧，令我叹为观止。

现在我确乎是浪费了半周时间在这上面。不过能在 1024 这个独特的二进制日，能够向大家展示这份成果，尤其是我一天写完的这 1147 行 43547 byte 的 ols.h 代码。有和我一样喜欢把时间浪费在研究这种东西上的朋友，我对此感到很幸运。

最后再次感谢矩阵群、yyc、ChatGPT、dyh 老师以及 tby 老师。