题目链接：
hdu: http://acm.hdu.edu.cn/showproblem.php?pid=5171
bc(中文): http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=567&pid=1002
题意：
给你初始的一堆数，每次从中找出两个最大的数相加再加入其中，求最后这n+k个数的和
题解：
初始堆中最大的两个数和后面的k个数会构成一个类似斐波那契数列。因此后面的和可用递推来求，由于k比较大，所以吧递推公式写成矩阵形式，用快速幂加速。
1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 7 const int maxn = 101010; 8 const int mod = 10000007; 9 typedef long long LL; 10 11 struct Matrix { 12 int n, m; 13 int val[11][11]; 14 Matrix(int n, int m) :n(n), m(m) {} 15 Matrix() {} 16 void init(int n, int m) { this->n = n; this->m = m; } 17 friend Matrix operator *(const Matrix& mat1, const Matrix& mat2) { 18 Matrix ret(mat1.n, mat2.m); 19 for (int i = 0; i < ret.n; i++) { 20 for (int j = 0; j < ret.m; j++) { 21 ret.val[i][j] = 0; 22 for (int k = 0; k < mat1.m; k++) { 23 ret.val[i][j] += (LL)mat1.val[i][k] * mat2.val[k][j] % mod; 24 ret.val[i][j] %= mod; 25 } 26 } 27 } 28 return ret; 29 } 30 }; 31 32 void power(Matrix& mat, int n, Matrix& ans) { 33 while (n) { 34 if (n & 1) ans = mat*ans; 35 mat = mat*mat; 36 n /= 2; 37 } 38 } 39 40 int arr[maxn]; 41 int n, k; 42 Matrix mat, ans; 43 44 void init() { 45 mat.init(3, 3); 46 mat.val[0][0] = 1; mat.val[0][1] = 1; mat.val[0][2] = 1; 47 mat.val[1][0] = 0; mat.val[1][1] = 1; mat.val[1][2] = 1; 48 mat.val[2][0] = 0; mat.val[2][1] = 1; mat.val[2][2] = 0; 49 ans.init(3, 1); 50 ans.val[0][0] = arr[n - 2] + arr[n - 1]; 51 ans.val[1][0] = arr[n - 1]; 52 ans.val[2][0] = arr[n - 2]; 53 } 54 55 int main() { 56 while (scanf("%d%d",&n,&k)==2&&n>1) { 57 for (int i = 0; i < n; i++) scanf("%d", arr + i); 58 sort(arr, arr + n); 59 LL sum = 0; 60 for (int i = 0; i < n - 2; i++) { 61 sum += arr[i]; sum %= mod; 62 } 63 init(); 64 power(mat,k, ans); 65 sum = (sum + ans.val[0][0]) % mod; 66 printf("%d ", sum); 67 } 68 return 0; 69 }