← 返回题目列表

AtCoder · abc450_e

H. 斐波那契字符串

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

给你字符串 X 和 Y。定义字符串序列 S_1, S_2, \dots 如下。

  • S_1 = X
  • S_2 = Y
  • 对于 i \geq 3, S_i 是串联的 S_{i-1} 和 S_{i-2} 按此顺序。

对于每个 i = 1, 2, \ldots, Q,回答以下问题。

问题:给定整数 L_i, R_i 和一个角色 C_i。查找字符出现了多少次 C_i 出现在 L_i-th 通过 R_i- 第一个字符 S_{10^{18}}.

约束

  • X 和 Y 是小写英文字母的字符串,长度介于 1 和 10^4,包括在内。
  • 1 \leq Q \leq 10^5
  • 1 \leq L_i \leq R_i \leq 10^{18}
  • C_i 是一个小写英文字母。
  • 所有给定的数值均为整数。

输入

输入由标准输入按以下格式给出:

X
Y
Q
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_Q R_Q C_Q

输出

输出 Q 行。
的 i- 第行应包含多少次字符 C_i 出现在 L_i-th 通过 R_i- 第一个字符 S_{10^{18}}.


示例输入 1

a
b
6
2 7 a
1 3 b
3 7 b
1 9 c
1 1000000000000000000 b
1000000000000000000 1000000000000000000 a

示例输出 1

3
2
3
0
618033988749894848
1

S_3, S_4, S_5 是 ba, bab, babba。

S_{10^{18}} is babbababbabba...,第二个到第七个字符包含三次 a.