hdu 4990 Reading comprehension (构造矩阵,快速幂)

题目链接

题意:

给出了一段程序,程序实际算的是f[n] = (f[n-1] + n%2)%m的值,其中f[1]=1,给出n,m(1E9),问f[n]

思路:

显然是矩阵快速幂,终点在于构造矩阵。

通过经验可得(这次真的是经验了。。。其实也挺容易的,要点大概在于先把需要的项列在一起,然后增加0或者多个,为了转移需要的辅助项。

根据当前列和下一列,手动构造转移矩阵)

转移矩阵M为

[2, 1,0]

[0,-1,1]

[0,0 ,1]

 

4A..都是一个原因。。矩阵乘法那里。。。就算你%了m..也是两个1E9在相乘。。。然后就炸了23333,改成LL即可。

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz