まず、壁を \(A\) 個と \(B\) 個に分けます。便宜上、前者をグループA、後者をグループBと呼びます。

簡単に言えば、グループAについて \(3^A\) 通り全探索を行い、それに合うようなグループBの個数を \(O(1)\) で求められるようにするのが目標です。以下に詳細を説明します。

まず、グループBの壁をそれぞれ \(3\) 色のうちいずれかで塗ることを考えます。このとき、グループBの壁の塗り方を \(3*B\) bitで次のように表現します。(便宜上、これをグループBの表現と呼びます。)

はじめ全てのbitは 0 になっている。グループBの i 番目の壁を、赤色としたときは 3*i 番目のbitを 1 に、緑色としたときは 3*i+1 番目のbitを 1 に、青色としたときは 3*i+2 番目のbitを 1 にする。

次に、グループAの壁をそれぞれ \(3\) 色のうちいずれかで塗ることを考えます。このとき、グループAの壁の塗り方を \(3*B\) bitで次のように表現します。(便宜上、これをグループAの表現と呼びます。)

はじめ全てのbitは 0 になっている。グループAの既に色で塗られている壁と見比べたとき、グループBの i 番目の壁を、赤色としても問題ないときは 3*i 番目のbitを 1 に、赤色としても問題ないときは 3*i+1 番目のbitを 1 に、赤色としても問題ないときは 3*i+2 番目のbitを 1 にする。

このように表現したとき、数え上げるべきものは次のように言い表せます。

グループAの色の塗り方とグループBの色の塗り方の組であって、以下の 3 条件

- グループA内の壁同士で条件を破らない
- グループB内の壁同士で条件を破らない
- グループAの表現である 3*B bitが、グループBの表現である 3*B bitを包含する

を全て満たすもの。

そこで、あらかじめ グループB側を全探索してから高速ゼータ変換することで、各グループAの塗り方に対して \(O(1)\) で組むことができるグループBの塗り方の総数を求めることができます。

時間計算量は \(O(3^A+B2^{3B})\) となっており、\(N=22\) では \(A=15,B=7\) とすると十分高速に動きます。