hdu 5950 Recursive sequence (构造矩阵,快速幂)

题目链接

题意:

给f[1],f[2],n,f[i] = 2*f[i-2] + f[i-1] + i^4,求f[n]的值。

思路:

很容易想到矩阵,但是i^4不是线性的差评,我们可以拆一下

i^4=(i-1+1)^4,然后二项式展开即可

i^4=(i-1)^4 + 4*(i-1)^3 + 6(i-1)^2 + 4(i-1) + 1

所以为了维护i^4这一项,需要(i-1)^4,(i-1)^3,(i-1)^2,(i-1),1,

再加上f[i-1]和f[i-2]两项,一共7项。

然后构造矩阵为

16沈阳 onsite的题,当时好像写了一个小时,现在看来,果然是个人尽皆知的傻逼题orz

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz