入力される行列を\(A\)として、\(\{1,2,\cdots,N\}\) の部分集合 \(S\) に対して、

\(I_S = \begin{cases} A_{ij} 　(i\in Sかつj\in S、または i \notin Sかつj \notin S )\\ -A_{ij} 　(\text{otherwise}) \end{cases} \)

と定めて、\(2^N\)個ある全ての部分集合\(S\)について、\(I_S\)を出力するとACが得られます。

以下では正当性を証明します。

・\(M\)の条件

\(M=2^N \leq 256\)です。

・行列式の条件

\(I_S\) は \(A\) に対して以下の操作を \(1\leq i \leq N\) について行うことで得られる行列です。

操作: \(i \in S\) ならば \(A\) の \(i\) 行目と \(i\) 列目を \(-1\) 倍する

行列のある行や列を \(-1\) 倍すると行列式も \(-1\) 倍されるので、上記の操作で行列式は不変です。任意の \(S\) に対して、 \(det(I_S)=det(A)\) です。

・和の条件

\(I_S\) の対角成分は常に \(A\) に等しいので、総和の対角成分は \(A\) の \(M\) 倍です。

\(I_S\) の非対角成分、 つまり \(i \neq j\) なる \(i\) 行 \(j\) 列目の成分について考察します。(\(1 \leq i , j \leq N\))

\(i \in S\) の場合、 \(i\) 行 \(j\) 列目の成分は \(j\in S\) ならば \(A_{ij}\) ,　\(j\notin S\) ならば \(-A_{ij}\) になりますが、\(i\)を含む集合について、\(j\)を含む集合と\(j\)を含まない集合は同じ数あり、和を取ると打ち消し合います。

\(i\notin S\)の場合でも、同様の議論を行うことで、総和が\(0\)になることが示せます。

\(S\)として、\(1\)を含むもののみを考えて、出力しても、同様にACできます。 この場合、\(M=2^{N-1}\)で構築できます。