GTY's birthday gift

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1760 Accepted Submission(s): 685

Problem Description

FFZ's birthday is coming. GTY wants to give a gift to ZZF. He asked his gay friends what he should give to ZZF. One of them said, 'Nothing is more interesting than a number multiset.' So GTY decided to make a multiset for ZZF. Multiset can contain elements with same values. Because GTY wants to finish the gift as soon as possible, he will use JURUO magic. It allows him to choose two numbers a and b(

Input

Multi test cases (about 3) . The first line contains two integers n and k (

Output

For each case , print the maximum sum of the multiset (

Sample Input

3 2 3 6 2

Sample Output

Source

BestCoder Round #29

Recommend

hujie

题意：

已经存在一个大小为n的集合，现在可以任意从中找到两个数，把它们的和加入集合中，这样的操作执行k次，那么这个集合的总和最大可以是多少？

题解：

可以推出斐波那契数列，那么就用矩阵快速幂求前n项，以及前n项和。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 #define rep(i,s,t) for(int (i)=(s); (i)<=(t); (i)++)
13 #define ms(a,b) memset((a),(b),sizeof((a)))
14 using namespace std;
15 typedef long long LL;
16 const int INF = 2e9;
17 const LL LNF = 9e18;
18 const double eps = 1e-6;
19 const int mod = 10000007;
20 const int maxn = 100000+10;
21 
22 int n,k;
23 int a[maxn];
24 
25 struct MAT
26 {
27     LL mat[5][5];
28     void init() {
29         rep(i,1,3) rep(j,1,3)
30             mat[i][j] = (i==j);
31     }
32 };
33 
34 MAT mul(MAT x, MAT y)
35 {
36     MAT s;
37     ms(s.mat,0);
38     rep(i,1,3)  rep(j,1,3) rep(k,1,3)
39         s.mat[i][j] += (1LL*x.mat[i][k]*y.mat[k][j])%mod, s.mat[i][j] %= mod;
40     return s;
41 }
42 
43 MAT qpow(MAT x, int y)
44 {
45     MAT s;
46     s.init();
47     while(y)
48     {
49         if(y&1)  s = mul(s,x);
50         x = mul(x,x);
51         y >>= 1;
52     }
53     return s;
54 }
55 
56 int main()
57 {
58     while(scanf("%d%d",&n,&k)!=EOF)
59     {
60         rep(i,1,n)
61             scanf("%lld",&a[i]);
62 
63         sort(a+1,a+1+n);
64         LL ans = 0;
65         rep(i,1,n)
66             ans += a[i], ans %= mod;
67 
68         if(k==1)
69         {
70             ans += (a[n-1]+a[n])%mod, ans %= mod;
71             cout<<ans<<endl;
72             continue;
73         }
74 
75         MAT s;
76         ms(s.mat,0);
77         s.mat[1][1] = s.mat[1][2] = s.mat[1][3] = 1;
78         s.mat[2][2] = s.mat[2][3] = s.mat[3][2] = 1;
79         s = qpow(s,k-2);
80 
81         ans += (1LL*(2*a[n-1]+3*a[n])*s.mat[1][1])%mod, ans %= mod;
82         ans += (1LL*(1*a[n-1]+2*a[n])*s.mat[1][2])%mod, ans %= mod;
83         ans += (1LL*(1*a[n-1]+1*a[n])*s.mat[1][3])%mod, ans %= mod;
84         cout<<ans<<endl;
85     }
86 }

View Code