CF575A Fibonotci

Fibonotci 数列是一个递归整数数列，其递推关系为： $$ F_{n} = s_{n-1} \cdot F_{n-1} + s_{n-2} \cdot F_{n-2} $$ 其中 $F_{0} = 0, F_{1} = 1$。数列 $s$ 是一个无限且“几乎循环”的数列，其循环节长度为 $N$。“几乎循环”数列的定义是：对于 $i \geq N$，除了有限个 $s_{i}$ 外，都有 $s_{i} = s_{i\,\bmod\,N}$。 下面是一个循环节长度为 $4$ 的“几乎循环”数列例子： $$ s = (5, 3, 8, 11, 5, 3, 7, 11, 5, 3, 8, 11, \ldots) $$ 注意，只有 $s_{6}$ 的数值与 $s_{2}$ 不同（$s_{6} = 7$，$s_{2} = 8$）。 现在已知 $s_{0}, s_{1}, \ldots, s_{N-1}$ 以及所有 $i \geq N$ 且 $s_{i} \neq s_{i \bmod N}$ 的 $s_{i}$ 的取值。 请计算 $F_{K} \bmod P$。

第一行包含两个整数 $K$ 和 $P$。 第二行包含一个整数 $N$。 第三行包含 $N$ 个用空格隔开的整数，表示数列 $s$ 的前 $N$ 项。 第四行包含一个整数 $M$，表示满足 $s_{j} \neq s_{j \bmod N}$ 的 $s_{j}$ 的个数。 接下来 $M$ 行，每行包含两个整数 $j$ 和 $v$，表示 $s_{j} = v$ 且 $s_{j} \neq s_{j \bmod N}$。所有 $j$ 均不相同。 - $1 \le N, M \le 50000$ - $0 \le K \le 10^{18}$ - $1 \le P \le 10^{9}$ - $1 \le s_{i} \le 10^{9}$，$i = 0,1,\ldots,N-1$ - $N \le j \le 10^{18}$ - $1 \le v \le 10^{9}$ - 所有数值均为整数。

输出一个整数，等于 $F_K \bmod P$。

由 ChatGPT 5 翻译