問題一覧 > 通常問題

No.1725 [Cherry 3rd Tune D] 無言の言葉

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 46
作問者 : 👑 KazunKazun / テスター : tatyamtatyam stoqstoq
2 ProblemId : 5339 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-01-01 23:20:15

問題文

文字列 $S,T$ に対して, $|S|, S \oplus T, \overline{S}$ をそれぞれ以下のように定義する.

  • $|S|$ を文字列 $S$ の長さとする.
  • $S \oplus T$ を $S, T$ をこの順に連結した文字列とする.
  • $\overline{S}$ を $S$ を反転させた文字列とする.
また, 文字列 $S$ と $1 \leq l \leq r \leq |S|$ に対して, $S[l:r]$ で$S$ の ($1$ -indexed で) $l$ 文字目から $r$ 文字目 (両端共に含む) の連続部分文字列とする. (21:46 訂正 $1$ -index → $1$ -indexed)

空ではない英小文字からなる文字列 $X,Y$ が与えられる. このとき, 正の整数 $n$ に対して, $F_n$ を以下で定める.

  • $F_1=X$
  • $F_n=F_{n-1} \oplus Y \oplus \overline{F_{n-1}} \quad (n \geq 2)$ (2023年01月01日 23:20, $n \geq 2$ を追加)

$Q$ 個のクエリが与えられる. $i~(1 \leq i \leq Q)$ 番目のクエリでは整数 $L_i, R_i~(L_i \leq R_i)$ 及び, 英小文字 $C_i$ が与えられるので, $F_{10^{100}} [L_i:R_i]$ に $C_i$ がいくつあるかを求めよ.

制約

  • $X, Y$ は英小文字からなる文字列
  • $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$ は整数
  • $C_i$ は英小文字

入力

入力は以下の形式で標準入力から与えられる. 
$X$
$Y$
$Q$
$L_1$ $R_1$ $C_1$
$\vdots$
$L_Q$ $R_Q$ $C_Q$

出力

出力は $Q$ 行からなる. $i~(1 \leq i \leq Q)$ 行目には, $i$ 番目のクエリに対する答えを出力せよ. また, $Q$ 行目の最後にも改行を忘れないこと.

サンプル

サンプル1
入力
ab
c
3
4 9 a
2 8 b
3 15 c
出力
2
3
5

$F_1,F_2,F_3$ はそれぞれ

  • $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
である. ここで, $F_{10^{100}} [1:15]=$ abcbacabcbacabc であることから, 以下の事がわかる.
  • $F_{10^{100}} [4:9]=$ bacabc に a は $2$ 個ある. (21:41 訂正 (10 → 9))
  • $F_{10^{100}} [2:8]=$ bcbacab に b は $3$ 個ある.
  • $F_{10^{100}} [3:15]=$ cbacabcbacabc に cは $5$ 個ある.

サンプル2
入力
yukicoder
cherry
5
46 4646 c
12345 67890 r
3333333 7777777 o
141421 356237 b
10 1000000000 y
出力
613
11109
296297
0
133333333

$F_{10^{100}}$ に全く現れない英小文字が指定される場合もある.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。