おおよその流れは 部分点解法 と同じです。

\(M := HW + 1\) とし、簡単のため \(H \leq W\) を仮定します。 また、整数 \(n\) が素数 \(p\) で割り切れる最大の回数を \(n_p\) で表すことにします。

M が素べきでない合成数のとき

構築可能であるとすれば \(R = 0\) に限ります。 このとき、構築可能性の必要条件として

\(M\) のすべての素因数 \(p\) に対して、

\( \begin{aligned} &\left\lfloor\frac{H}{2} \right\rfloor \times \left\lfloor\frac{W}{2} \right\rfloor \leq \left\lfloor\frac{HW}{p} \right\rfloor \\ &M_p (H-1) (W-1) \leq \sum_{n=1}^{HW} 4 \times \min(n_p, M_p) \, \text{ if } H \geq 3 \\ &M_p (H-1) (W-1) \leq \sum_{n=1}^{HW} 2 \times \min(n_p, M_p) \, \text{ if } H = 2 \end{aligned} \)

が成り立つ、という条件があります。

式の導出

$1$ つめの不等式は各 $2 \times 2$ マスに $p$ の倍数が最低 $1$ つ存在するという要請から従います。
残りの不等式は素因数 $p$ の需要数 (左辺) と供給数の最大値 (右辺) から導出されます。

この条件が成り立つ \((H, W)\) を制約の範囲で探すと \((H, W) = (3, 3), (3, 13), (5, 7), (11, 13)\) が該当します。

このうち、\((H, W) = (3, 3), (3, 13), (5, 7)\) には条件を満たす構築が存在し、\((H, W) = (11, 13)\) には存在しません。

\((H, W, R) =(3, 3, 0)\) の構築例

{ 1,  2,  3}, 
{ 4,  5,  6}, 
{ 7,  8,  9}

\((H, W, R) =(3, 13, 0)\) の構築例

{ 1,  2,  3,  6,  7,  9, 11, 13, 14, 17, 18, 19, 21}, 
{ 5,  8, 15, 16, 25, 24, 35, 32, 10,  4, 20, 12, 30}, 
{22, 23, 26, 27, 28, 29, 31, 33, 34, 36, 37, 38, 39}

\((H, W, R) =(5, 7, 0)\) の構築例

{ 1, 14, 11, 17, 23, 28, 32}, 
{ 2,  9, 10, 18,  4, 27,  8}, 
{ 5, 30, 13, 19, 25, 29, 34}, 
{ 3,  6, 15, 12, 21, 24, 33}, 
{ 7, 22, 16, 20, 26, 31, 35}

M が素べきかつ合成数のとき

\(M = p^e\) と表すことにすると、上と同様の議論により構築可能性の必要条件として

• \(R = 0\) のとき

\( \begin{aligned} e (H-1) (W-1) \leq \sum_{n=1}^{HW} 4 \times \min(n_p, e) \, \text{ if } H \geq 3 \\ e (H-1) (W-1) \leq \sum_{n=1}^{HW} 2 \times \min(n_p, e) \, \text{ if } H = 2 \end{aligned} \)

• \(R\) が \(p^{e-1}\) の倍数かつ \(R \neq 0\) のとき

\( \begin{aligned} (e-1) (H-1) (W-1) \leq \sum_{n=1}^{HW} 4 \times \min(n_p, e-1) \, \text{ if } H \geq 3 \\ (e-1) (H-1) (W-1) \leq \sum_{n=1}^{HW} 2 \times \min(n_p, e-1) \, \text{ if } H = 2 \end{aligned} \)

が挙げられます。

この条件が成り立つのは \((H, W, R) = (2, 4, 3k), (3, 5, 0), (3, 5, 8), (3, 8, 5k), (3, 21, 32) \, (k > 0)\) のときです。

(a) \((H, W, R) = (2, 4, 3k), M = 9\) のとき

次のような解が存在します

# R = 3
{3, 4, 6, 7}, 
{2, 5, 1, 8}

# R = 6
{6, 4, 3, 7}, 
{2, 5, 1, 8}

(b) \((H, W) = (3, 5), M = 16\) のとき

\(R = 0, 8\) の両方に解が存在します

# R = 0 
{ 1,  3,  2,  5,  7}, 
{ 6,  8, 10,  4, 12}, 
{ 9, 11, 14, 13, 15}

# R = 8 
{ 1,  3,  2,  5,  6}, 
{ 8,  7,  4,  9, 12}, 
{11, 13, 10, 15, 14}

(c) \((H, W, R) = (3, 8, 5k), M = 25\) のとき

このときも解が存在します。

# R = 5k
{  1,  19,  13,  18,  14,  21,  17,  22}, 
{ 5k,   9, 10k,   2, 20k,  16, 15k,  23}, 
{  7,  12,  11,   4,   3,   8,  24,   6}

(d) \((H, W, R) = (3, 21, 32), M = 64\) のとき

入出力例にあるように解は存在しません。

M が素数のとき

\(R > 0\) とします。\(M\) の原始根を底とする離散対数をとることで、次の条件を満たす構築が可能か考えることにします。

• \(0, 1, \ldots, M-2 = HW - 1\) がちょうど一度ずつ登場する
• どの \(2 \times 2\) 小行列をとっても、その中にある \(4\) 要素の和 \(\pmod{HW}\) が \(\log_r{R} \pmod{HW}\) に等しい。ただし、 \(\log_r{R}\) は \(r^{\log_r{R}} \equiv R \pmod{HW}\) を満たす、 \(0\) 以上 \(HW-1\) 以下の整数とする。

\(H, W\) がともに偶数のとき、構築は部分点解法と同様にできます。

\(H, W\) の一方が偶数、もう一方が奇数のとき、実はすべての \(R \gt 0\) に対して構築方法が存在します。

\((H, W) = (4, 7)\) のときの構築例

# 和が 0 (mod 4)
{ 0,  8,  1,  9,  2, 10,  3}, 
{ 7, 13,  6, 12,  5, 11,  4}
->
{ 0, 22,  1, 23,  2, 24,  3}, 
{ 7, 27,  6, 26,  5, 25,  4},
{14,  8, 15,  9, 16, 10, 17}, 
{21, 13, 20, 12, 19, 11, 18}

# 和が 2 (mod 4)
{  0,  -3,   4,  -7,   8, -11,  12},
{ -1,   2,  -5,   6,  -9,  10, -13},
{  1,  -4 ,  5,  -8,   9, -12,  13},
{ -2,   3,  -6,   7, -10,  11, -14}

# 和が 3 (mod 4)
{  0,  -1,   1,  -2,   2,  -3,   3},
{ -4,   4,  -5,   5,  -6,   6,  -7},
{  7,  -8,   8,  -9,   9, -10,  10},
{-11,  11, -12,  12, -13,  13, -14}

# 和 が 1(mod 4)
# 上を -1 倍したもの