No.1725 [Cherry 3rd Tune D] Silent Words
Problem Statement
For strings $S,T$, we define $|S|, S \oplus T, \overline{S}$ as follows.
- $|S|$ is the length of the string $S$.
- $S \oplus T$ is the string obtained by concatenating $S, T$ in this order.
- $\overline{S}$ is the string obtained by reversing $S$.
You are given non-empty strings $X,Y$ consisting of lowercase English letters. For a positive integer $n$, we define $F_n$ as follows.
- $F_1=X$
- $F_n=F_{n-1} \oplus Y \oplus \overline{F_{n-1}} \quad (n \geq 2)$ (January 1, 2023, 23:20: added $n \geq 2$)
You are given $Q$ queries. In the $i~(1 \leq i \leq Q)$-th query, you are given integers $L_i, R_i~(L_i \leq R_i)$ and a lowercase English letter $C_i$. Find how many occurrences of $C_i$ there are in $F_{10^{100}} [L_i:R_i]$.
Constraints
- $X, Y$ are strings consisting of lowercase English letters
- $1 \leq |X|, |Y| \leq 10^5$
- $1 \leq Q \leq 5 \times 10^4$
- $1 \leq L_i \leq R_i \leq 10^9$
- $Q, L_i, R_i$ are integers
- $C_i$ is a lowercase English letter
Input
The input is given from standard input in the following format.$X$ $Y$ $Q$ $L_1$ $R_1$ $C_1$ $\vdots$ $L_Q$ $R_Q$ $C_Q$
Output
The output consists of $Q$ lines. On the $i~(1 \leq i \leq Q)$-th line, print the answer to the $i$-th query. Do not forget to print a newline at the end of the $Q$-th line as well.
Sample
Sample 1
Input
ab c 3 4 9 a 2 8 b 3 15 c
Output
2 3 5
$F_1,F_2,F_3$ are as follows, respectively.
- $F_1=$
ab - $F_2=F_1 \oplus Y \oplus \overline{F_1}=$
ab$\oplus$c$\oplus$ba$=$abcba - $F_3=F_2 \oplus Y \oplus \overline{F_2}=$
abcba$\oplus$c$\oplus$abcba$=$abcbacabcba
abcbacabcbacabc, the following can be seen.
- $F_{10^{100}} [4:9]=$
bacabccontainsa$2$ times. (Corrected at 21:41 (10 → 9)) - $F_{10^{100}} [2:8]=$
bcbacabcontainsb$3$ times. - $F_{10^{100}} [3:15]=$
cbacabcbacabccontainsc$5$ times.
Sample 2
Input
yukicoder cherry 5 46 4646 c 12345 67890 r 3333333 7777777 o 141421 356237 b 10 1000000000 y
Output
613 11109 296297 0 133333333
A lowercase English letter that does not appear in $F_{10^{100}}$ at all may be specified.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun
tatyam
stoq