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次。
/* ***********************************************
Author :111qqz
Created Time :Tue 25 Oct 2016 07:00:23 PM CST
File Name :code/bzoj/4547.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const LL mod = 1E7+7;
const int N=1E5+7;
int n,k;
LL a[N];
LL a0,a1;
LL sum;
struct Mat
{
LL mat[2][2];
void clear()
{
ms(mat,0);
}
}M,M1;
Mat operator*(Mat a,Mat b)
{
Mat res;
res.clear();
for ( int i = 0 ; i < 2 ; i++)
for ( int j = 0 ; j < 2 ; j++)
for ( int k = 0 ; k < 2 ; k++)
res.mat[i][j] = (res.mat[i][j] + a.mat[i][k]*b.mat[k][j] ) %mod;
return res;
}
Mat operator ^ (Mat a,LL b)
{
Mat res;
res.clear();
for ( int i = 0 ; i < 2 ; i++) res.mat[i][i] = 1;
while (b>0)
{
if (b&1) res = res * a;
b = b >> 1LL;
a = a * a;
}
return res;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
scanf("%d%d",&n,&k);
for ( int i = 1 ; i <= n ;i++) scanf("%lld",&a[i]);
sum = 0 ;
sort(a+1,a+n+1);
a0 = a[n-1];
a1 = a[n];
//cout<<"a0:"<<a0<<" a1:"<<a1<<endl;
//
if (a1<0)
{
for ( int i = 1 ; i <= n ; i++) sum = ( sum + a[i] + mod ) %mod;
sum = (sum + k*(a0+a1+mod)%mod+mod)%mod;
printf("%lld\n",sum);
return 0;
}
for ( int i = 1 ;i <= n-2 ; i++) sum =( sum + a[i]+mod ) % mod;
if (a0<0)
{
LL num = -a0/a1+1;
// cout<<"num:"<<num<<endl;
if (num<=k)
{
k-=num;
sum = ( sum + num*a0%mod + (a1*(num-1))*num/2%mod +mod)%mod;
a0 = (a0 + a1 *num%mod)%mod;
if (a0>a1) swap(a0,a1);
}
}
Mat ans;
M.clear();
M1.clear();
ans.clear();
M.mat[0][1] = M.mat[1][0] = M.mat[1][1] = 1;
M1.mat[0][0] = a0;
M1.mat[1][0] = a1;
ans = (M^(k+2))*M1;
sum = (sum + ans.mat[1][0] - a1 + mod)%mod;
printf("%lld\n",sum);
return 0;
/*
if (a0<0)
{
LL num = (-a0)/a1 + 1;
// cout<<"num:"<<num<<endl;
if (k<=num)
{
for ( int i = 1 ; i <= n-2 ; i++) sum = (sum + a[i] + mod ) % mod;
sum = ( sum + a[n] + mod ) %mod;
num = k+1;
// cout<<"sum:"<<sum<<endl;
sum = (sum + (num*a0 + num*(num-1)/2*a1)%mod+mod)%mod;
printf("%lld\n",sum);
return 0;
}
k-=num;
for ( int i = 1 ; i <= n-2 ; i++) sum = (sum + a[i]+mod ) % mod;
sum = (sum + num*a0 + num*(num-1)/2*a1+mod)%mod;
a0 = a0 + num*a1;
//<F5printf("a0:%lld a1:%lld\n",a0,a1);
Mat ans;
M.clear();
M1.clear();
ans.clear();
M.mat[0][1] = M.mat[1][0] = M.mat[1][1] = 1;
M1.mat[0][0] = a0;
M1.mat[0][1] = a1;
ans = (M ^(k+2))*M1;
sum = (sum + ans.mat[1][0] - a1 + mod ) %mod;
printf("%lld\n",sum);
} */
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}