BZOJ 4547: Hdu5171 小奇的集合 (矩阵快速幂)
4547: Hdu5171 小奇的集合
Time Limit: 2 Sec Memory Limit: 256 MB Submit: 263 Solved: 113 [Submit][Status][Discuss]
Description
有一个大小为n的可重集S，小奇每次操作可以加入一个数a+b(a,b均属于S)，求k次操作后它可获得的S的和的最大
值。（数据保证这个值为非负数）
Input
第一行有两个整数n,k表示初始元素数量和操作数，第二行包含n个整数表示初始时可重集的元素。
对于100%的数据，有 n<=10^5，k<=10^9，|ai|<=10^5
Output
输出一个整数，表示和的最大值。答案对10000007取模。
Sample Input
2 2 3 6
Sample Output
33
HINT
Source
思路：同hdu 5171的区别在于，a可能为负数。
同样是设a0为次大值，a1为最大值。
根据a0,a1的正负分类讨论。
如果a1<0（此时a0一定也小于0）那么每次操作都是a0+a1,因为越加越小。
如果a0<0，需要计算需要几次运算，使得a0>=0。设需要num次。
原因是，类斐波那契数列的性质可以对于正数，也可以对于负数，但是如果有正数有负数，性质是不满足的。
因此如果num>k，说明一直都是负数，直接运算即可，如果num<=k，就需要先把负数部分用等差数列的方法处理掉。
然后再用矩阵快速幂的方法计算剩下的k-num次。
1/* ***********************************************
2Author :111qqz
3Created Time :Tue 25 Oct 2016 07:00:23 PM CST
4File Name :code/bzoj/4547.cpp
5 ************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const LL mod = 1E7+7;
32const int N=1E5+7;
33int n,k;
34LL a[N];
35LL a0,a1;
36LL sum;
37struct Mat
38{
39 LL mat[2][2];
40 void clear()
41 {
42 ms(mat,0);
43 }
44}M,M1;
45Mat operator*(Mat a,Mat b)
46{
47 Mat res;
48 res.clear();
49 for ( int i = 0 ; i < 2 ; i++)
50 for ( int j = 0 ; j < 2 ; j++)
51 for ( int k = 0 ; k < 2 ; k++)
52 res.mat[i][j] = (res.mat[i][j] + a.mat[i][k]*b.mat[k][j] ) %mod;
53 return res;
54}
55Mat operator ^ (Mat a,LL b)
56{
57 Mat res;
58 res.clear();
59 for ( int i = 0 ; i < 2 ; i++) res.mat[i][i] = 1;
60 while (b>0)
61 {
62 if (b&1) res = res * a;
63 b = b >> 1LL;
64 a = a * a;
65 }
66 return res;
67}
68int main()
69{
70#ifndef ONLINE_JUDGE
71 freopen("code/in.txt","r",stdin);
72#endif
73 scanf("%d%d",&n,&k);
74 for ( int i = 1 ; i <= n ;i++) scanf("%lld",&a[i]);
75 sum = 0 ;
76 sort(a+1,a+n+1);
77 a0 = a[n-1];
78 a1 = a[n];
79 //cout<<"a0:"<<a0<<" a1:"<<a1<<endl;
80 //
81 if (a1<0)
82 {
83 for ( int i = 1 ; i <= n ; i++) sum = ( sum + a[i] + mod ) %mod;
84 sum = (sum + k*(a0+a1+mod)%mod+mod)%mod;
85 printf("%lld\n",sum);
86 return 0;
87 }
88 for ( int i = 1 ;i <= n-2 ; i++) sum =( sum + a[i]+mod ) % mod;
89 if (a0<0)
90 {
91 LL num = -a0/a1+1;
92// cout<<"num:"<<num<<endl;
93 if (num<=k)
94 {
95 k-=num;
96 sum = ( sum + num*a0%mod + (a1*(num-1))*num/2%mod +mod)%mod;
97 a0 = (a0 + a1 *num%mod)%mod;
98 if (a0>a1) swap(a0,a1);
99 }
100 }
101 Mat ans;
102 M.clear();
103 M1.clear();
104 ans.clear();
105 M.mat[0][1] = M.mat[1][0] = M.mat[1][1] = 1;
106 M1.mat[0][0] = a0;
107 M1.mat[1][0] = a1;
108 ans = (M^(k+2))*M1;
109 sum = (sum + ans.mat[1][0] - a1 + mod)%mod;
110 printf("%lld\n",sum);
111 return 0;
112 /*
113 if (a0<0)
114 {
115 LL num = (-a0)/a1 + 1;
116// cout<<"num:"<<num<<endl;
117 if (k<=num)
118 {
119 for ( int i = 1 ; i <= n-2 ; i++) sum = (sum + a[i] + mod ) % mod;
120 sum = ( sum + a[n] + mod ) %mod;
121 num = k+1;
122// cout<<"sum:"<<sum<<endl;
123 sum = (sum + (num*a0 + num*(num-1)/2*a1)%mod+mod)%mod;
124 printf("%lld\n",sum);
125 return 0;
126 }
127 k-=num;
128 for ( int i = 1 ; i <= n-2 ; i++) sum = (sum + a[i]+mod ) % mod;
129 sum = (sum + num*a0 + num*(num-1)/2*a1+mod)%mod;
130 a0 = a0 + num*a1;
131//<F5printf("a0:%lld a1:%lld\n",a0,a1);
132 Mat ans;
133 M.clear();
134 M1.clear();
135 ans.clear();
136 M.mat[0][1] = M.mat[1][0] = M.mat[1][1] = 1;
137 M1.mat[0][0] = a0;
138 M1.mat[0][1] = a1;
139 ans = (M ^(k+2))*M1;
140 sum = (sum + ans.mat[1][0] - a1 + mod ) %mod;
141 printf("%lld\n",sum);
142 } */
143#ifndef ONLINE_JUDGE
144 fclose(stdin);
145#endif
146 return 0;
147}