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

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 46
作問者 : 👑

Kazun / テスター :

tatyam

stoq

2 ProblemId : 5339 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2023-01-01 23:20:15

文字列 $S,T$ に対して, $|S|, S \oplus T, \overline{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$ 
 $Q$ 
 $L_1$   $R_1$   $C_1$ 
 $\vdots$ 
 $L_Q$   $R_Q$   $C_Q$

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

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 であることから, 以下の事がわかる.

yukicoder
cherry
5
46 4646 c
12345 67890 r
3333333 7777777 o
141421 356237 b
10 1000000000 y

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

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