\(T\) の長さを \(M\) とおきます。

\(S_N\) は非常に長い文字列となる可能性がありますが、\(T\) に対して操作を行ったとき、操作後の文字列としてあり得るものは \(T\) を rotate したもの、\(T\) を rotate したものを反転したもののみです。このアイディアを整理します。

• a, b からなる文字列 \(U\) に対して以下のように \(U_a \in \Z / M\Z, U_b \in \Z / 2\Z\) を定める。この \(U_a, U_b\) のみから文字列への操作の挙動は確定する。なお、文字列を \(k\) rotate したものに置き換えるとは、先頭の文字を末尾に移動する操作を \(k\) 回行うことを指す。

• • \(U\) が文字列を \(k\) rotate したものに置き換えるとき、\(U_a = k, U_b = 0\) とする。
• • \(U\) が文字列を \(k\) rotate した後に反転したものに置き換えるとき、\(U_a = k, U_b = 1\) とする。

文字列を結合したときの挙動について計算すると、以下のようになることがわかります。なお、数学の用語を用いれば、これは二面体群 \(D_M\) です（これを \(D_{2M}\) と呼ぶ流儀も存在します）。

• 文字列 \(X, Y\) をこの順に結合して \(U\) が得られたとする。

• • \(X_b = 0\) のとき、\(U_a = X_a + Y_a, U_b = Y_b\) である。
• • \(X_b = 1\) のとき、\(U_a = X_a - Y_a, U_b = 1 + Y_b\) である。

\(a_i \coloneqq {S_i}_a, b_i \coloneqq {S_i}_b\) とおきます。目標は、\(a_N, b_N\) を計算することです。

\(b_i\) の周期性

\(i > K\) なる任意の整数 \(i\) に対して \(b_i = b_{i - 1} + b_{i - 2} + \ldots + b_{i - K}, b_{i + 1} = b_i + b_{i - 1} + \ldots + b_{i - K + 1}\) が成り立つため、これらを比較して \(b_{i + 1} = b_{i - K}\) を得ます。したがって \(b_i\) は周期 \(K + 1\) を持ち、\(b_N\) は高速に計算できることが分かります。

\(a_i\) の計算

文字列を結合したときの挙動について考えると、\(i > K\) としたとき \(c_{i, j} \in \{ \pm 1 \}\) を用いて \(a_i = c_{i, i - 1}a_{i - 1} + c_{i, i - 2}a_{i - 2}+ \ldots +c_{i, i - K}a_{i - K}\) と表すことができることがわかります。 ここで係数 \(c_{i, j}\) が \(b_{i - 1}, b_{i - 2}, \ldots, b_{j + 1}\) から決まる（具体的には \(c_{i, j} = (-1)^{b_{i - 1} + b_{i - 2} + \ldots, b_{j + 1}}\) となる）ことと \(b_i\) が周期 \(K + 1\) を持つことを利用すると、\(c_{i, j} = c_{i + K + 1, j + K + 1}\) となっていることがわかります。したがって、ある整数係数の行列 \(A\) が存在し、任意の非負整数 \(i\) について \(\begin{pmatrix} a_{(K + 1)(i + 1) + 1} \\ a_{(K + 1)(i + 1) + 2} \\ \vdots \\ a_{(K + 1)(i + 2)} \end{pmatrix} = A \begin{pmatrix} a_{(K + 1)i + 1} \\ a_{(K + 1)i + 2} \\ \vdots \\ a_{(K + 1)(i + 1)} \end{pmatrix}\) と表すことができます。

また、\(A\) は実際に上の行から順に文字列を結合したときの式に従って計算していくことができます。\(A\) が求まった後には行列累乗を用いて\(A^{\lfloor\frac{N - 1}{K + 1} \rfloor}\) を計算することで \(a_N\) の値を求めることができます。

\(i \leq K+1\) なる \(i\) に対する \(a_i, b_i\) の計算は \(O(\sum|S_i|)\) 時間、\(A\) の計算は \(O(K^3)\) 時間、行列累乗は \(O(K^3 \log N)\) 時間、最終的な文字列の計算は \(O(M)\) 時間で行え、全体として時間計算量は \(O(\sum |S_i| + K^3 \log N + M)\) です。