← 返回题目列表

Codeforces · 1634/F

F. 斐波那契加法

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

斐波那契加法是对整数数组 $$$X$$$ 的运算,由索引 $$$l$$$ 和 $$$r$$$ 参数化。斐波那契加法将 $$$X_l$$$ 增加 $$$F_1$$$,将 $$$X_{l + 1}$$$ 增加 $$$F_2$$$,依此类推,直到 $$$X_r$$$ 增加 $$$F_{r - l + 1}$$$。

$$$F_i$$$ 表示第 $$$i$$$ 个斐波那契数($$$F_1 = 1$$$、$$$F_2 = 1$$$、$$$F_{i} = F_{i - 1} + F_{i - 2}$$$ for $$$i > 2$$$),并且所有操作均以模进行$$$MOD$$$。

给定两个长度相同的数组 $$$A$$$ 和 $$$B$$$。我们将要求您使用不同的参数对这些数组执行几次斐波那契加法,每次操作后您必须报告数组 $$$A$$$ 和 $$$B$$$ 是否等于对 $$$MOD$$$ 取模。

输入

第一行包含 3 个数字 $$$n$$$、$$$q$$$ 和 $$$MOD$$$ ($$$1 \le n, q \le 3\cdot 10^5, 1 \le MOD \le 10^9+7$$$) — 数组的长度、运算次数以及所有运算执行的模数。

第二行包含 $$$n$$$ 数字 — 数组 $$$A$$$ ($$$0 \le A_i < MOD$$$)。

第三行还包含 $$$n$$$ 数字 — 数组 $$$B$$$ ($$$0 \le B_i < MOD$$$)。

接下来的 $$$q$$$ 行包含字符 $$$c$$$ 和两个数字 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) - 操作参数。如果$$$c$$$为“A”,则对数组$$$A$$$进行斐波那契加法运算,如果为“B”,则对$$$B$$$进行斐波那契加法运算。

输出

每次操作后,如果数组相等则打印“YES”(不带引号),否则打印“NO”。字母大小写无关紧要。

示例

输入 #1

3 5 3
2 2 1
0 0 0
A 1 3
A 1 3
B 1 1
B 2 2
A 3 3

输出 #1

YES
NO
NO
NO
YES

输入 #2

5 3 10
2 5 0 3 5
3 5 8 2 5
B 2 3
B 3 4
A 1 2

输出 #2

NO
NO
YES

注意

条件测试说明:

- 最初$$$A=[2,2,1]$$$,$$$B=[0,0,0]$$$。
- 运算“A 1 3”后:$$$A=[0,0,0]$$$,$$$B=[0,0,0]$$$(加法以 3 为模)。
- 操作“A 1 3”后:$$$A=[1,1,2]$$$,$$$B=[0,0,0]$$$。
- 操作“B 1 1”后:$$$A=[1,1,2]$$$,$$$B=[1,0,0]$$$。
- 操作“B 2 2”后:$$$A=[1,1,2]$$$,$$$B=[1,1,0]$$$。
- 操作“A 3 3”后:$$$A=[1,1,0]$$$,$$$B=[1,1,0]$$$。