整数 \(T\) が与えられたとき、以下の \(6\) つの条件を考えます。

• 条件 \(1\) : \(T\) が \(0,1\) のいずれかである
• 条件 \(2\) : \(T\) が \(0,1,2\) のいずれかである
• 条件 \(3\) : \(T\) が \(1,2\) のいずれかである
• 条件 \(4\) : \(T = 0\) である
• 条件 \(5\) : \(T = 1\) である
• 条件 \(6\) : \(T = 2\) である

また、\(3\) 進表記した際に \(i\) 桁目が条件 \(X_i\) を満たすような位置にある爆弾の合計個数を \(f(X_1,X_2, \ldots, X_N)\) とします。

入力や出力の内容を整理すると、各 \(i\) について \(X_i \in \lbrace 1,2,3 \rbrace\) を満たす \(X\) について \(f(X)\) が与えられていて、各 \(i\) について \(X_i \in \lbrace 4,5,6 \rbrace\) を満たす \(X\) について \(f(X)\) を答えればよいです。

ここで、

\( \begin{aligned} f(X_1,X_2, \ldots, X_{i-1}, 4, X_{i+1}, \ldots, X_N) &= f(X_1,X_2, \ldots, X_{i-1}, 2, X_{i+1}, \ldots, X_N) - f(X_1,X_2, \ldots, X_{i-1}, 3, X_{i+1}, \ldots, X_N) \\ f(X_1,X_2, \ldots, X_{i-1}, 5, X_{i+1}, \ldots, X_N) &= f(X_1,X_2, \ldots, X_{i-1}, 1, X_{i+1}, \ldots, X_N) + f(X_1,X_2, \ldots, X_{i-1}, 3, X_{i+1}, \ldots, X_N) -f(X_1,X_2, \ldots, X_{i-1}, 2, X_{i+1}, \ldots, X_N) \\ f(X_1,X_2, \ldots, X_{i-1}, 6, X_{i+1}, \ldots, X_N) &= f(X_1,X_2, \ldots, X_{i-1}, 2, X_{i+1}, \ldots, X_N) - f(X_1,X_2, \ldots, X_{i-1}, 1, X_{i+1}, \ldots, X_N) \end{aligned} \)
であるため、 \(i = 1,2, \ldots, N\) の順で \(j \leq i\) ならば \(X_j \in \lbrace 4,5,6 \rbrace\)、\(j > i\) ならば \(X_j \in \lbrace 1,2,3 \rbrace\)を満たすすべての \(X\) について \(f(X)\) を求めていけばよいです。

この操作は、\(N\) 次元累積和や高速ゼータ変換の応用と捉えることもできます。