斐丢波丢那陈契 - 题目

传统 2000 ms 256 MiB

标准 IO

文本比较 admin 标签

众所周知，丢丢陈是位数学巨擘。因此，爱慕他的女生非常之多。他时常因不知如何挑选女生而愁眉苦脸，为此，他发明了斐丢波丢那陈契数列，决定挑选会算这个数列的女生作为女友，该数列定义如下：

\begin{equation} F_n=\left\{ \begin{array}{rcl} 0 &,& {n = 0}\\ 1 &,& {n = 1}\\ s_{n-1}F_{n-1} + s_{n-2}F_{n-2} &,& {n \geq 2} \end{array} \right. \end{equation}

其中 $\{s_i\}$ 是无穷数列，且满足改变 $m$ 个数之后数列变为无限循环数列，例如 $s = (5,3,8,11,5,3,7,11,5,3,8,11,…)$ 。

现在给出数列 $\{s_i\}$ 的循环节长度 $n$ 和前 $n$ 项的内容，并告知将其变为无限循环数列所需改变的项(保证不包括前 $n$ 项中的任意一项)的位置 $j_i$ 和改变前的值 $v_i$ 。

现在对给定 $k,\ p$ ，请帮助女生们求出 $F_k$ 对 $p$ 作除法后的余数。

注意：题中所给下标均从 $0$ 开始。

测试数据有不超过 $15$ 组，用 EOF 标志表示输入结束，对于每一组数据满足：

第一行为两个整数 $k,p(0\leq k\leq 10^{18},\ 1\leq p\leq 10^9)$ ；

第二行为一个整数 $n(1\leq n\leq 5\times 10^4)$ ；

接下来一行共 $n$ 个整数，表示 $\{s_i\}$ 的前 $n$ 项， $(1\leq s_i\leq 10^9,\ i=0,\ 1,\ \ldots,\ n-1)$ ；

第四行为一个整数 $m(1\leq m\leq 5\times 10^4)$ ，表示将其变为无限循环数列所需改变的项的数目；

接下来 $m$ 行，其中第 $i$ 行有两个整数 $j_i,\ v_i(n\leq j_i\leq 10^{18},1\leq v_i\leq 10^9)$ 。

对于每组数据，输出一行共一个整数，表示 $F_k$ 对 $p$ 作除法后的余数。

#109. 斐丢波丢那陈契