Original proposer: toam

This problem can be solved with a recursive function.

For a string \(T\), let \(|T|\) denote its length.

For \(i \geq 2\), \(S_i\) is a prefix of \(S_{i+1}\). Thus, we can take the minimum \(K\) with \(|S_K| \geq \max R_i\) and inspect \(S_K\) instead of \(S_{10^{18}}\). Since \(|S_i|\) is at least the \(i\)-th Fibonacci number, \(K=O(\log\max_Ri)\). (Particularly, in our problem \(K=88\).)

The number of occurrences within the \(L\)-th through \(R\)-th characters is the number of occurrences within the first \(R\) characters, subtracted by that within the first \((L-1)\). Therefore, the original problem can be answered by solving the following question twice: “how many occurrences are there within the first \(N\) characters?” We will now tackle this problem.

Let \(f_c(k,n)\) be the number of occurrences of character \(c\) among the first \(n\) characters of \(S_k\). For \(k\geq 3\), \(S_k\) is a concatenation of \(S_{k-1}\) and \(S_{k-2}\) in this order, so depending on \(n\leq |S_{k-1}|\) we obtain:

\(f_c(k,n)=\begin{cases} \#(c\text{ in the first }n\text{ characters of }X) & \text{if }k=1 \\ \#(c\text{ in the first }n\text{ characters of }Y) & \text{if }k=2 \\ f_c(k-1,x) & \text{if } k\geq 3 \text{ and } n \leq |S_{k-1}| \\ \#(c\text{ in }S_{k-1}) + f_c(k-2, n-|S_{k-1}|) & \text{if } k\geq 3 \text{ and } n > |S_{k-1}|. \end{cases}\)

(The notation \(\#(c \ldots)\) reads “the number of occurrences of character \(c\)….”) Therefore, we may precalculate

• \(|S_1|,\ldots,|S_K|\)
• \(\#(c\text{ in the first }i\text{ characters of }X)\)
• \(\#(c\text{ in the first }i\text{ characters of }Y)\)
• \(\#(c\text{ in }S_K)\)

and memorize them for \(O(1)\) retrieval, the recursive relations allow us to compute \(f_c(K,n)\) in \(O(K)\) time.

Hence, the problem has been solved in a total of \(O(\sigma(|X|+|Y|+\log \max R_i)+Q\log\max R_i)\) time including the precalculation, where \(\sigma\) is the size of the alphabet.