题目给定左上角的 $R\times C$ 矩形，保证已有部分每行、每列内部没有重复数字；需要判断能否补成 $n\times n$ 拉丁方，并在有解时输出方案，$n\le 500$。
记数字 $x$ 在已知矩形中出现了 $f_x$ 次。可补全的充要条件是：
$$ \forall x\in[1,n],\qquad f_x\ge R+C-n. $$
这就是本题对应的 Ryser 条件。下面不仅证明它，还直接据此构造答案。
必要性很直接：最终前 $R$ 行中必须各有一个 $x$，所以还需要补入 $R-f_x$ 个 $x$。这些数只能放在后 $n-C$ 列中，而每列最多放一个，因此必须有 $R-f_x\le n-C$。
接下来证明充分性。
先把已知部分扩展成 $R\times n$。 建立一个二分图，左侧是前 $R$ 行，右侧是 $n$ 个数字。如果第 $i$ 行缺少数字 $x$，就连边 $(i,x)$。
设 $d=n-C$。每个行顶点的度数都是 $d$，数字 $x$ 对应顶点的度数是 $R-f_x$。由判定条件，所有数字顶点的度数都不超过 $d$。
现在增加 $n-R$ 个虚拟行顶点，使左右两侧各有 $n$ 个顶点。将每个虚拟行的度数补到 $d$，并将每个数字顶点的度数也补到 $d$。数字 $x$ 还需要补的度数为 $d-R+f_x$，这些缺口都非负，总和恰好是 $(n-R)d$，所以可以用双指针贪心补边。
这里允许补出重边：这些边只与虚拟行相连，最终不会写入答案。因此，不需要为了保持简单图而再求一次流。
这样得到一个 $d$-正则二分多重图。把它的边染成 $d$ 种颜色，使同一顶点相邻的边颜色互不相同。将颜色 $t$ 对应到新增的第 $C+t$ 列：真实边 $(i,x)$ 染成颜色 $t$，就令 $A_{i,C+t}=x$。
由于每个真实行顶点恰好有 $d$ 条边，它会在每个新增列中恰好填入一个数字；由于同一数字顶点相邻的边颜色不同，同一新增列不会出现重复数字。于是得到合法的 $R\times n$ 拉丁矩形。
再把它扩展成 $n\times n$。 这次左侧放 $n$ 个列顶点，右侧仍放 $n$ 个数字。列 $j$ 中缺少数字 $x$，就连边 $(j,x)$。
每列缺少 $n-R$ 个数字；每个数字已经在前 $R$ 行出现了恰好 $R$ 次，而且位于不同列，因此也恰好在 $n-R$ 列中缺失。这张图已经是 $(n-R)$-正则二分图。
将它染成 $n-R$ 种颜色，每种颜色对应一个新增行即可。
因此，问题只剩下：如何快速地把一个两侧各有 $n$ 个顶点的 $d$-正则二分多重图分成 $d$ 个完美匹配？
确定性快速边染色
以下所有图的左右两侧都各有 $n$ 个顶点。原图有 $m=nd$ 条边，每条边有独立编号；只有求匹配时临时复制的边，才使用重数压缩存储。
先考虑偶数度数的拆分。
如果一张二分图的所有顶点度数都是偶数，那么可以把每个连通分量的欧拉回路上的边交替分到两边。二分图中的闭合回路长度为偶数，因此每个顶点分到两边的度数相等。特别地，$2k$-正则图可以在线性时间拆成两个 $k$-正则图。反复拆分即可处理度数为 $2$ 的幂的情况，这也是基于欧拉拆分的边染色方法的基本工具。
对于带压缩重数的边，也不需要把它们展开。设某条边的重数为 $w$，先向两边各分配 $\lfloor w/2\rfloor$ 份；如果 $w$ 为奇数，则留下一个副本。所有剩余副本构成的图仍然每个顶点度数为偶数，再对它做欧拉拆分。
所以，一次拆分的复杂度与边记录的数量成正比，而不是与重数之和成正比。
当 $d$ 是 $2$ 的幂时，直接不断二分，直到每张图都是 $1$-正则图。每一层处理 $nd$ 条边，共 $\log d$ 层，复杂度为 $O(nd\log d)$。
真正的问题是奇数度数。我们先给出一个确定性 $O(nd\log(nd))$ 的完美匹配算法。这里使用 Alon 的压缩重边构造，不需要调用匈牙利算法、Hopcroft–Karp 或最大流。
取不小于 $nd$ 的最小的 $2$ 的幂 $P$，令 $\alpha=\lfloor P/d\rfloor$、$\beta=P-\alpha d$。
把原图的每条边复制 $\alpha$ 份，再在左右编号相同的顶点之间各加 $\beta$ 条临时边。这些临时边不一定属于原图，将它们称为“坏边”。新图中每个顶点的度数都是 $\alpha d+\beta=P$。
此时坏边总数为 $n\beta$，并且 $\beta< d$，所以 $n\beta< nd\le P$。
不断将当前正则图等分，并且每次只保留坏边数量较少的那一半。每次保留下来的度数减半，坏边总数也至少减半。经过 $\log P$ 次拆分后，得到一张 $1$-正则图，其坏边数量不超过 $n\beta/P< 1$。
坏边数量是整数，因此最终没有任何坏边。这张 $1$-正则图就是原图的一个完美匹配。
虽然复制后的边数可能很大，但每条原边只保存一个重数，再加至多 $n$ 条坏边记录。每轮始终只有 $O(nd)$ 条记录，总共 $O(\log(nd))$ 轮，因此时间复杂度为 $O(nd\log(nd))$，空间复杂度为 $O(nd)$。
有了匹配算法，还不能简单地“奇数度数先删匹配，偶数度数递归两边”，然后直接声称总复杂度只有一个对数。为了明确消除递归中的额外对数，使用只对一半调用通用算法，另一半凑成 $2$ 的幂的合并方式。这个单侧递归框架与上面的匹配构造共同给出了确定性的 $O(m\log m)$ 边染色算法。
具体来说，对于偶数度数 $d=2k$：
先拆成两个 $k$-正则图 $G_0,G_1$，只递归染色 $G_0$，得到 $k$ 个完美匹配。
令 $p$ 为不小于 $k$ 的最小的 $2$ 的幂。从 $G_0$ 中拿出 $p-k$ 个完整的颜色类，加入 $G_1$。由于一个颜色类就是一个完美匹配，加入后的 $G_1$ 恰好变成 $p$-正则图，可以直接用欧拉拆分染色。
$G_0$ 剩下 $2k-p$ 个颜色类，$G_1$ 新产生 $p$ 个颜色类，合起来正好是 $2k=d$ 种颜色。
例如 $d=10$ 时，先拆成两张 $5$-正则图。递归染好第一张，再从中拿出三个完美匹配加入第二张，使第二张成为 $8$-正则图。第一张保留两种颜色，第二张直接拆出八种颜色，总共十种。
对于奇数 $d$，先求一个完美匹配，为它单独使用一种颜色，然后处理剩下的 $(d-1)$-正则图。
因此，将“奇数时删匹配”和紧接着的偶数处理合并来看，通用递归满足：
$$ F(d)\le F(\lfloor d/2\rfloor)+O(nd\log(nd)), $$
从而 $F(d)=O(nd\log(nd))$。因为本题中 $d\le n$，所以一次边染色是 $O(nd\log n)$。
两次构图的度数分别是 $n-C$ 和 $n-R$，总时间为 $O(n^2+n(2n-R-C)\log n)$，最坏为 $O(n^2\log n)$。各层保留的图大小按几何级数递减，匹配算法又只保留一个分支，因此总空间为 $O(n^2)$。
无解时，不需要分配完整答案矩阵，统计出现次数后即可在 $O(RC+n)$ 时间内结束。