題目連結:
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比較大,是以吧遞推公式寫成矩陣形式,用快速幂加速。
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5CO4YTNwUTO1gTMtADOwYTN4UzMxcjM0AjNxAjMtIDMykDM48CX0AjNxAjMvwlMwITOwgzLcd2bsJ2Lc12bj5ycn9Gbi52YuUTMwIzcldWYtl2Lc9CX6MHc0RHaiojIsJye.png)
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\n", sum);
67 }
68 return 0;
69 }