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

By Hzwer

思路:同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}