別解として、ゼータ変換の行列による解釈を応用した機械的な解法を説明します。(ゼータ変換・メビウス変換・アダマール変換などの変換はこの解説と同様の解釈で理解することができます。)

入力と答えを縦ベクトル \(A, B\) で表します。\(A\) と \(B\) の間には

\[M_N[i][j] = (1 \text{ if i と j は近い位置である else } 0)\]

を満たすような \(3^N \times 3^N\) 行列 \(M_N\) を用いて

\[A = M_N B\]

という関係式が成り立ちます。

まず、本題から少し逸れますが、\(B\) が与えられたときに \(A\) を高速に計算する問題を考えます。
これは \(M_N\) の行列の形に注目すると高速な計算方法が導出できます。
\(M_N\) は 3 進数の \(N-1\) 桁目に注目することで以下の形に分解できることがわかります。(\(I_{N-1}\) は \(3^{N-1} \times 3^{N-1}\) の単位行列)

\[ \begin{aligned} M_N &= \left( \begin{array}{ccc} M_{N-1} & M_{N-1} & 0 \\ M_{N-1} & M_{N-1} & M_{N-1} \\ 0 & M_{N-1} & M_{N-1} \\ \end{array} \right) \\ &= \left( \begin{array}{ccc} I_{N-1} & I_{N-1} & 0 \\ I_{N-1} & I_{N-1} & I_{N-1} \\ 0 & I_{N-1} & I_{N-1} \\ \end{array} \right) \left( \begin{array}{ccc} M_{N-1} & 0 & 0 \\ 0 & M_{N-1} & 0 \\ 0 & 0 & M_{N-1} \\ \end{array} \right) \end{aligned} \]

上式から分割統治を利用して \(B\) から \(A\) を求める解法を導出できます。
詳しく説明します。\(M_N B\) を計算するのに、\(M_N\) を上式のように 2 個に分解して、まず右の行列を \(B\) に作用させたあとに左の行列を作用させるという順番で計算します。
すると、右の行列は長さ \(3^{N-1}\) のベクトルから長さ \(3^{N-1}\) のベクトルへの変換が \(3\) 個並んだ形をしているので、3 分割すれば再帰的に計算できます。また、左の行列は、\(0 \leq i \leq 3^{n-1}\) について \(B[i + 0], B[i + 3^{n-1}], B[i + 2 \times 3^{n-1}]\) に行列

\[ \left( \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \\ \end{array} \right) \]

を作用させる形になっているので、これを愚直に計算します。
よって、\(B \gets M_N B\) は次のような疑似コードで記述できる inplace な再帰 DP で計算出来て、これは \(\mathrm{O}(N 3^N)\) で十分高速に動作します。

void f(vector<int>& B, int N, int L) {
  if(N == 0) return;
  int d = 1;
  for(int i = 0; i < N - 1; i++) d *= 3;

  // 右の行列に対応する部分
  f(B, N - 1, L);
  f(B, N - 1, L + d);
  f(B, N - 1, L + d * 2);

  // 左の行列に対応する部分
  for(int i = 0; i < d; i++) {
    int x = B[L + i] + B[L + i + d];
    int y = B[L + i] + B[L + i + d] + B[L + i + 2 * d];
    int z = B[L + i + d] + B[L + i + 2 * d];
    B[L + i] = x;
    B[L + i + d] = y;
    B[L + i + 2 * d] = z;
  }
}

さて、元の問題では \(A\) から \(B\) を求める、つまり

\[B = M^{-1}A\]

の右辺を計算する問題です。
これは非自明ですが、\(3 \times 3\) 行列を作用させる部分で、作用させる行列を

\[ \left( \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \\ \end{array} \right) \]

から、作用させる行列の逆行列

\[ \left( \begin{array}{ccc} 0 & 1 & -1 \\ 1 & -1 & 1 \\ -1 & 1 & 0 \\ \end{array} \right) \]

に変えるだけで \(A\) から \(B\) への変換になることが証明できます。(詳しくはページ下部にある記事のリンク先を参考にしてください。) また、この変換によって得られる \(B\) が正当な答えであることは入力の制約と \(M\) の正則性から示されます。
よってこの問題を \(\mathrm{O}(N 3^N)\) で解くことができて、これは十分高速です。(実装例, バタフライ演算と呼ばれる DP の非再帰化を利用しています)

• 参考: ryuhei さんの記事