NOI2013 矩阵游戏

题意描述

有一个n*m的矩阵,用F[i][j]表示矩阵第i行第j列上的元素。

满足:

以下是一个3*4的例子

1 4 7 10
26 29 32 35
76 79 82 85

编程任务:给出n和m,要求输出F[n][m]
数据范围:
图片1.jpg

解法一:直接求

时间复杂度:O(n*m)
期望得分:20

解法二:矩阵乘法+二进制快速幂

因为考虑到解法一在不停的做重复工,所以马上就想到矩阵乘法。
但是怎样设计矩阵呢?
观察矩阵乘法公式:

还有我们的递推式:

发现了什么? 好像什么也没发现。
再仔细看看,假设C[1][1]就是我们要求的下一个数K,那么A[1][1]就是L,B[1][1]就是他的系数a,B[2][1]就 是另一个系数b,那么A[1][2]便为1。

至此,矩阵已完全浮现在我们眼前。

设置一个1*2的初始矩阵INIT。
第一位用来保存数值,第二位保存系数1。

设置一个转移矩阵A。
第一列的两个数在上面已经解释
而第二列的两个数是为了维护矩阵INIT的系数1不变。

同样的设置另一个转移矩阵B

那么求出答案矩阵

求幂的时候用二进制快速幂即可。
ANS[1][1]便是答案。

时间复杂度: 因为求二进制快速幂时要用到高精度除法,所以时间复杂度是O(位数*位数)
期望得分:70

解法三:解法二的优化版本

1)将二进制快速幂改成十进制的快速幂,省去高精度除法所浪费的时间。
2)矩阵相乘时,因为矩阵的特殊性,可以O(1)求出,减小常数。

时间复杂度:O(位数*10)
期望得分:100

解法四:费马小定理优化

费马小定理: 若P是一个质数,A是一个小于N的正整数则

考虑到时间都是花在快速幂上,所以我们可以观察一下。

由于答案所模的数是一个质数,所以可以令N=Nmod(P-1),然后再用快速幂。
时间复杂度:O(位数+logP)
期望得分:100

comments powered by Disqus