「HLOI2016」序列问题

题目描述

现定义序列它的第 项为：

定义 以及 。

其中， 是一个无限长的，几乎循环的一个数字序列，它的循环节长度为 ，也就是说，通常会有 。但是 中也存在少数元素并不符合这个循环节，也就是说，会有若干个元素，。

现在给出序列 的循环节，以及 中不符合循环的位置以及值，求 。

输入

输入的第一行有两个整数 和 ；

第二行是一个整数 ；

第三行包含 个正整数，表示循环节中所有的数字；

接下来一行是一个整数 。接下来的 行，每行包含两个整数 和 ，表示在序列 中不符合循环节的位置以及相应位置上的值，即 。

输出

输出包含一个整数，即相应输入文件的答案。

样例输入

42 1248493
5
5 2 4 1 6
5
9 3
8 4
21 21
10 18
24 10

样例输出

232959

数据范围及约定

对于 的数据：；

对于 的数据：；

对于 的数据：。

时间与空间限制

时间限制：，空间限制：。

题解

一看 这么大快速幂逃不掉了……

一看递推关系矩阵逃不掉了……

所以矩阵快速幂逃不掉了。

MDZZ 怎么搞矩阵？

这回在化学课上推公式……

看出什么来了吗？反正我看了一天

可以看出这个 只与 有关……

假如能搞出一个矩阵的话，可以借鉴分块思想，将一个循环节看成一个块，将整个块内的值求出后，跑矩阵快速幂，之后零散部分暴力。

可是有修改……？

就将修改看成断点，假如断点处于同一块内，暴力即可，如果不在，零散暴力，整块快速幂。 时间为 ，这样可以过 ……

优化的是零散部分，因为要不停计算零散部分，这些零散部分还是循环的，所以可以用线段树优化。

所以，怎么构造矩阵？

两个矩阵，一个是处理影响的，一个是统计答案的。

统计答案的矩阵是一个 的矩阵：

当然也可以写成 的，其余补 即可。

处理影响的矩阵是一个 的矩阵：

遇到断点答案矩阵暴力乘矩阵即可，此矩阵为：

其中 为需要修改的位置， 为变换成的数。

这还没完，因为矩阵与 位置也有关，还需要乘：

这样就可以了。

时间复杂度为 ，空间复杂度为 。

还有一些许多细节需要注意……具体参见代码。

代码见这里。