問題へのリンク

解法

5 重対角成分のみ考えればよいというところまで、公式解説と同じです。公式解説では（例示にすぎませんが）5 マス分の状態を管理するとよいとありましたが、私は 1 マス分で解けましたので共有させていただこうかとです。

まず、そのまま取り出すと最初と最後だけ 2 マスずつ足りませんから、適宜調整して 3, 2, 3, 2, 3, 2, ..., 2, 3 のようにケンケンパの形にしておきましょう。すると、下図のようになります。囲ってある青い 3 マスや赤い 4 マスに、xor 0 制約があります。

一旦、ケンケンパの「外側」の 4 行が決まっていると思いましょう。すると青い 3 マスにおいては外側 2 マスが決まっていることになりますが、これにより真ん中が確定します。

また赤い 4 マスにおいては上下 2 マスが決まっていることになり、これにより左右が等しいか異なるかが決まります。

しかし実際には「外側」の 4 行は決まっていたり決まっていなかったりしますから、そこを頑張っていきましょう。

青色制約と赤色制約を左から順に見ていって、左から順に、中央の行のすでに決まったマスのうち最も右にあるマスに何が書いてあるかを管理する DP をするとよいです。これは、詳しくご説明しようと思うと大変ですから、例でご勘弁いただけるとです。

下記はサンプル 2 です。緑で囲った部分がケンケンパです。はみ出た部分は、( 0, None ), ( 0, None ) にしておくとよいです。

こうしてできるサンプル 2 のケンケンパがこちらです。制約を満たすように、残りのマスに 0 か 1 を埋めて行きましょう！

このような遷移グラフになり、五重対角成分に限った答えは 0 + 16 = 16、ここに非五重対角成分の埋め方 2 通りをかけるとよいです。