题意：已经存在一个长度为n的序列，现在可以任意从中找到两个数，把它们的和加入序列，这样的操作执行k次，那么这个序列总和最大可以是多少。
分析可得，每次找到次大值a，最大值b，加入a+b会让和sum最大，那么依次要加入的数为a+b，a+2b，2a+3b，3a+5b，5a+8b。。。可以看出a的系数分别是1，1，2，3，5，8。。。而b的系数分别是1，2，3，5，8。。。那么这不就是斐波那契数列吗，我们可以利用矩阵快速幂来求出斐波那契数列的值（理由是斐波那契序列是可以用2*2矩阵的k次方来表示的，想知道详情可以先做一下POJ 3070），但是这道题需要求的是斐波那契的和，而不是第k项，这里就要用到一个公式sumk=F（k+2）-1，那么我们就可以利用快速幂得到第k+2项的值，再减1（a的系数之和ansa），第k+3项的值，再减2（b的系数之和ansb，因为b的系数少啦一个1，所以需要求出第k+3项的值），最后ansa*a+ansb*b就是添加的数之和啦，再加上已有的数之和，就是最终答案啦。#include<stdio.h> #include<string.h> #include<queue> #include<math.h> #include<stdlib.h> #include<algorithm> using namespace std; const int N=1e6+10; const int INF=0x3f3f3f3f; const int MOD=1e7+7; typedef long long LL; struct node { LL m[2][2]; }ans, tmp, cnt; int c[N]; node Multiply(node a, node b) ///计算两个矩阵相乘之后的矩阵 { int i, j, k; for (i = 0; i < 2; i++) { for (j = 0; j < 2; j++) { cnt.m[i][j] = 0; for (k = 0; k < 2; k++) cnt.m[i][j] = (cnt.m[i][j]+a.m[i][k]*b.m[k][j])%MOD; } } return cnt; } LL Matrix_power(LL n) { ans.m[0][0] = ans.m[1][1] = 1; ans.m[0][1] = ans.m[1][0] = 0; tmp.m[0][0] = tmp.m[0][1] = tmp.m[1][0] = 1; tmp.m[1][1] = 0; while (n) ///和快速幂求法一致 { if (n % 2 != 0) ans = Multiply(ans, tmp); tmp = Multiply(tmp, tmp); n /= 2; } return ans.m[0][1]; ///由于第n个Fibonacci数存在于{Fn+1，Fn，Fn，Fn-1}中，所以我们返回（0，1）位置上的元素即可 } int main () { LL k, sum, a, b, ansa, ansb, suma, sumb; int i, n; while (scanf("%d%lld", &n, &k) != EOF) { sum = 0; for (i = 0; i < n; i++) { scanf("%lld", &c[i]); sum += c[i]; sum %= MOD; } sort(c, c+n); a = c[n-2]; b = c[n-1]; ansa = Matrix_power(k+2); ansb = Matrix_power(k+3); suma = (ansa-1)*a%MOD; sumb = (ansb-2)*b%MOD; sum = (sum+suma+sumb)%MOD; printf("%lld\n", sum); } return 0; }
HDU 5171 GTY's birthday gift（BestCoder Round #29）
原文：http://www.cnblogs.com/syhandll/p/4978846.html