GTY's birthday gift
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
a,b∈S), and add a+b
Input
2≤n≤100000,1≤k≤1000000000). The second line contains n elements ai ( 1≤ai≤100000)separated by spaces , indicating the multiset S .
Output
mod 10000007).
Sample Input
3 2 3 6 2
Sample Output
35
解题思路:
想要和最大,那么每次必定从集合里面拿出最大的两个出来相加,然后k次后面就类似斐波那契数列了。
由斐波那契数列公式知:Fn=Fn-1+Fn-2,求和公式有Sn=Sn-1+Fn.因此用这两个公式构造矩阵,进行矩阵快速幂。
Sn-1 | 1 1 0| Sn
Fn * | 0 1 1| =Fn+1
Fn-1 | 0 1 0| Fn
然后ans=(Sn+(sum-a[n-1]-a[n-2]))%mod(sum为原集合总和,然后减去最大的两个,加上k次后的序列之和(即斐波那契数列和))。