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

题目链接

题意:

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

思路:

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

通过经验可得(这次真的是经验了。。。其实也挺容易的,要点大概在于先把需要的项列在一起,然后增[……]

Read more