A14773 | Fibonacci Additions
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
One of my most productive days was throwing away 1,000 lines of code.
— Ken Thompson
Fibonacci addition is an operation on an array $X$ of integers, parametrized by indices $l$ and $r$ . Fibonacci addition increases $X_l$ by $F_1$ , increases $X_{l + 1}$ by $F_2$ , and so on up to $X_r$ which is increased by $F_{r - l + 1}$ .
$F_i$ denotes the $i$ -th Fibonacci number ( $F_1 = 1$ , $F_2 = 1$ , $F_{i} = F_{i - 1} + F_{i - 2}$ for $i > 2$ ), and all operations are performed modulo $MOD$ .
You are given two arrays $A$ and $B$ of the same length. We will ask you to perform several Fibonacci additions on these arrays with different parameters, and after each operation you have to report whether arrays $A$ and $B$ are equal modulo $MOD$ .
— Ken Thompson
Fibonacci addition is an operation on an array $X$ of integers, parametrized by indices $l$ and $r$ . Fibonacci addition increases $X_l$ by $F_1$ , increases $X_{l + 1}$ by $F_2$ , and so on up to $X_r$ which is increased by $F_{r - l + 1}$ .
$F_i$ denotes the $i$ -th Fibonacci number ( $F_1 = 1$ , $F_2 = 1$ , $F_{i} = F_{i - 1} + F_{i - 2}$ for $i > 2$ ), and all operations are performed modulo $MOD$ .
You are given two arrays $A$ and $B$ of the same length. We will ask you to perform several Fibonacci additions on these arrays with different parameters, and after each operation you have to report whether arrays $A$ and $B$ are equal modulo $MOD$ .
输入格式
The first line contains 3 numbers $n$ , $q$ and $MOD$ ( $1 \le n, q \le 3\cdot 10^5, 1 \le MOD \le 10^9+7$ ) — the length of the arrays, the number of operations, and the number modulo which all operations are performed.
The second line contains $n$ numbers — array $A$ ( $0 \le A_i < MOD$ ).
The third line also contains $n$ numbers — array $B$ ( $0 \le B_i < MOD$ ).
The next $q$ lines contain character $c$ and two numbers $l$ and $r$ ( $1 \le l \le r \le n$ ) — operation parameters. If $c$ is "A", Fibonacci addition is to be performed on array $A$ , and if it is is "B", the operation is to be performed on $B$ .
The second line contains $n$ numbers — array $A$ ( $0 \le A_i < MOD$ ).
The third line also contains $n$ numbers — array $B$ ( $0 \le B_i < MOD$ ).
The next $q$ lines contain character $c$ and two numbers $l$ and $r$ ( $1 \le l \le r \le n$ ) — operation parameters. If $c$ is "A", Fibonacci addition is to be performed on array $A$ , and if it is is "B", the operation is to be performed on $B$ .
输出格式
After each operation, print "YES" (without quotes) if the arrays are equal and "NO" otherwise. Letter case does not matter.
输入输出样例
输入 #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
Explanation of the test from the condition:
- Initially $A=[2,2,1]$ , $B=[0,0,0]$ .
- After operation "A 1 3": $A=[0,0,0]$ , $B=[0,0,0]$ (addition is modulo 3).
- After operation "A 1 3": $A=[1,1,2]$ , $B=[0,0,0]$ .
- After operation "B 1 1": $A=[1,1,2]$ , $B=[1,0,0]$ .
- After operation "B 2 2": $A=[1,1,2]$ , $B=[1,1,0]$ .
- After operation "A 3 3": $A=[1,1,0]$ , $B=[1,1,0]$ .
- Initially $A=[2,2,1]$ , $B=[0,0,0]$ .
- After operation "A 1 3": $A=[0,0,0]$ , $B=[0,0,0]$ (addition is modulo 3).
- After operation "A 1 3": $A=[1,1,2]$ , $B=[0,0,0]$ .
- After operation "B 1 1": $A=[1,1,2]$ , $B=[1,0,0]$ .
- After operation "B 2 2": $A=[1,1,2]$ , $B=[1,1,0]$ .
- After operation "A 3 3": $A=[1,1,0]$ , $B=[1,1,0]$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted