[1] \(O(NK\cdot (2/3)^K)\) 時間での計算

\(k\) 回操作時点での数列の項数を \(N_k\) とすれば、\(N_k\) は次のように計算できます：\(N_{k+1} = \lfloor \frac{2N_k}{3}\rfloor\). 特に本問題で計算対象となる数列の項数 \(N_K\) は \(O(K)\) 時間で計算できます。この項数を \(M\) と書くことにします。

数列 \(A = (a_0, a_1, \ldots)\) に対して操作を行った結果の数列を \(B = (b_0, b_1, \ldots)\) とするとき、\(b_i\) は次の規則で計算できます：\(b_i = a_{j}\)、ただし \(j = \lfloor \frac{3i+2}{2}\rfloor\).

したがって、\(f(i) = \lfloor\frac{3i+2}{2}\rfloor\) と書くことにすると、本問題は次のように言い換えることができます：

\(\sum_{n=0}^{M-1} \bigl(f^K(n) + 1\bigr)\) を求めよ。

ここで、\(f^K\) は \(f\) の \(K\) 回合成です。

これをそのまま計算するという方法の計算量は \(O(MK)\) です。\(M\leq N\cdot (2/3)^K\) なので、\(O(NK\cdot (2/3)^K)\) 時間で解くことができます。

[2] \(O(K\cdot 2^K)\) 時間での計算

\(f\) の合成 \(f^K\) は、次の周期性を持つことが帰納的に確かめられます：\(f^K(n + 2^K) = f^K(n) + 3^K\).

\(0\leq i < 2^K\) に対する \(f^K(i)\) を前計算したあとで、\(n\equiv i \pmod{2^K}\) となる \(n\) の寄与をまとめて計算することで、\(O(K\cdot 2^K)\) 時間での計算が可能です。

[3] \(O((K+\log N)\cdot 2^{K/2})\) 時間での計算

\(K = X + Y\) となる \(X, Y\) とおき、\(f^K(n) = f^Y(f^X(n))\) と分解します。また、\(f^X, f^Y\) について [2] と同様の前計算を行っておきます。

各 \(i\) に対して、\(n\equiv i \pmod{2^X}\) となる \(n\) の寄与をまとめて計算することを考えると、次のような計算が必要になります：

• \(\sum_{j}f^Y(a + 3^X j)\) を求めよ

これは\(f^Y(a) + \cdots + f^Y(a + (2^k-1)3^X)\) の形の和をすべて事前計算しておくことで、高速に計算できます。

\(X = \lceil N/2\rceil\), \(Y = \lfloor N/2\rfloor\) とすることで、例えば \(O((K+\log N) \cdot 2^{K/2})\) などの計算量で解くことができます。

[4] まとめ

[1], [3] の解法を使い分けることで、本問題は次の計算量で解くことができます：\(O(\min(NK\cdot (2/3)^K, (K+\log N) \cdot 2^{K/2}))\).

例えば \(K > 40\) ならば [1] の方法、\(K\leq 40\) ならば [3] の方法で解くことによって、正解を得ることができます。

なお、次のような高速化が可能ですが、どれも実装せずとも制約の実行時間に収まることを想定しています。

• [1] における \(f^K(n)\) の計算を、[3] と同様の考え方で高速化する。
• [3] における \(f^X(i)\) の前計算を \(O(2^X)\) 時間で行う。
• [3] における \(\sum_j f^Y(a + 3^Xj)\) の計算を、\(3^X\) 個ごとの累積和の事前計算により、前計算 \(O(2^Y)\)、クエリ \(O(1)\) で計算する。したがって、[3] 全体を \(O(2^{K/2})\) 時間で行う。