hdu 5171 GTY’s birthday gift (矩阵快速幂)

题目链接

题意:给出n,k,以及n个正数,把n个数放在一个集合里,进行k次操作,每次操作取最大的数和次大的数放进集合。问k次操作结束后,集合中所有数的和。

思路:假设初始时刻,次大和最大分别为a0,a1,那么得到的就是一个类斐波那契数列。初始为a0,a1,fn = fn-1 + fn

最后求和。

 

screenshot-from-2016-10-25-18-48-09

利用这个性质。。。

我们直接构造完矩阵。。。求出F(n+2)即可。。

需要注意。。。矩阵中每一项是小于1E7+7的。。。矩乘的时候会爆int…

所以mat要用LL存。。我好傻啊。。。

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz