HDU6395 Sequence

2018 Multi-University Training Contest 7 T10

题面传送门

看数据范围,发现的数据范围很大,而又看到了,果断数论分块。

考虑数论分块后怎么做。

利用矩阵乘法可以构造出类似的形式的数列转移。

(按照题目中的变量名)

初始矩阵:

转移矩阵:

然后一边数论分块一边矩阵快速幂,时间复杂度

Tips:矩乘不满足交换律!!!被这点坑了好久。