問題一覧 > 通常問題

No.1725 [Cherry 3rd Tune D] Silent Words

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 47
作問者 : 👑 Kazun / テスター : tatyam stoq
お気に入りにしたユーザー ProblemId : 5339 / 自分の提出
問題文最終更新日: 2023-01-01 23:20:15
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 320 (Stray Bullet) (順位表) の他の問題:

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$.
Also, for a string $S$ and $1 \leq l \leq r \leq |S|$, $S[l:r]$ denotes the substring of $S$ from the $l$-th character to the $r$-th character (both ends inclusive, $1$ -indexed). (Corrected at 21:46: $1$ -index → $1$ -indexed)

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
Here, since $F_{10^{100}} [1:15]=$ abcbacabcbacabc, the following can be seen.
  • $F_{10^{100}} [4:9]=$ bacabc contains a $2$ times. (Corrected at 21:41 (10 → 9))
  • $F_{10^{100}} [2:8]=$ bcbacab contains b $3$ times.
  • $F_{10^{100}} [3:15]=$ cbacabcbacabc contains c $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もしくは右上の雲マークをクリックしてアカウントを作成してください。