#2032. 「SvR-2」令人为难的区间操作问题
「SvR-2」令人为难的区间操作问题
题目描述
小 F 正在研究斐波那契数列,他惊讶地发现,可以把这种数列 的定义式略作修改,得到 数列:
注意到 数列具有周期性,最小正周期 。
请注意这里 数列与数学上用其表示的双伽玛函数的区别。
小 F 找到一个长度为 的数列 ,他每次对其进行如下操作:
- 选定两个整数 ,满足 。
- 对于每个满足 的 ,将 加上 。
- 记录下本次操作(即第 次操作)的选定区间的长度 。
他一共进行了 次操作,操作后得到数列记作 ,同时记 。
不幸的是,小 F 把 和数列 都弄丢了,他只记得 和数列 。
现在,他想请你根据这些信息,求出 的奇偶,即 对 取模后的值。
输入格式
本题有多组数据。
第一行一个整数 ,表示数据组数。
接下来 行,描述每组数据。对于每组数据:
- 第一行一个整数 。
- 第二行 个整数,描述数列 。
- 第三行 个整数,描述数列 。
数据保证数列 一定可以经过若干操作变为数列 。
输出格式
对于每组数据,输出仅一行一个数,即 对 取模后的值。
样例
1
4
1 2 3 4
2 4 3 4
1
题目来源:洛谷 P9086