题目链接：
hdu:
bc(中文):
题意：
给你初始的一堆数，每次从中找出两个最大的数相加再加入其中，求最后这n+k个数的和
题解：
初始堆中最大的两个数和后面的k个数会构成一个类似斐波那契数列。因此后面的和可用递推来求，由于k比较大，所以吧递推公式写成矩阵形式，用快速幂加速。
1 #include2 #include 3 #include 4 #include 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\n", sum);67 }68 return 0;69 }