BZOJ 4547: Hdu5171 小奇的集合 (矩阵快速幂)

Posted by 111qqz on Wednesday, October 26, 2016

TOC

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次。

/* ***********************************************
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;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付