题意:已经存在一个长度为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