原案：toam

この問題は再帰関数を用いて解くことができます。

文字列 \(T\) の長さを \(|T|\) と表します。

\(i \geq 2\) のとき、 \(S_i\) は \(S_{i+1}\) の prefix です。よって、\(|S_K| \geq \max R_i\) となる最小の \(K\) をとり、\(S_{10^{18}}\) の代わりに \(S_K\) を考えてよいです。\(|S_i|\) は \(i\) 番目のフィボナッチ数以上になることから、 \(K=O(\log\max R_i)\) です。（特に今回は高々 \(88\) です）

\(L\) 文字目から \(R\) 文字目までの個数は「先頭から \(R\) 文字目までの個数」から「先頭から \(L-1\) 文字目までの個数」を引いたものです。よって「先頭から \(N\) 文字目までの個数は？」という形の問題を \(2\) 回解けばもとの問題に答えることができます。以下この問題を考えます。

\(f_c(k,n)\) を、 \(S_k\) の \(n\) 文字目までに含まれる文字 \(c\) の個数と定めます。\(k\geq 3\) なら \(S_k\) が \(S_{k-1}\) と \(S_{k-2}\) をこの順に連結した文字列であることから、\(n\leq |S_{k-1}|\) であるかどうかによって場合分けすることで、以下の式を得ます。

\(f_c(k,n)=\begin{cases} X \text { の } n \text{ 文字目までに含まれる } c \text{ の個数} & k=1 \text{ のとき} \\ Y \text { の } n \text{ 文字目までに含まれる } c \text{ の個数} & k=2 \text{ のとき} \\ f_c(k-1,x) & k\geq 3 \text{ かつ } n \leq |S_{k-1}| \text{ のとき}\\ (S_{k-1} \text{ に含まれる } c \text{ の個数}) + f_c(k-2,n-|S_{k-1}|) & k\geq 3 \text{ かつ } n > |S_{k-1}| \text{ のとき} \end{cases}\)

よって、予め

• \(|S_1|,\ldots,|S_K|\)
• \(X\) の先頭から \(i\) 文字目までに含まれる文字 \(c\) の個数
• \(Y\) の先頭から \(i\) 文字目までに含まれる文字 \(c\) の個数
• \(S_k\) に含まれる文字 \(c\) の個数

をそれぞれ前計算して \(O(1)\) で得られる状態にしておけば、この再帰を用いて \(f_c(K,n)\) に \(O(K)\) で答えることができます。

文字種数を \(\sigma\) として、前計算を含め \(O(\sigma(|X|+|Y|+\log \max R_i)+Q\log\max R_i)\) でこの問題を解くことができました。