111qqz的小窝

老年咸鱼冲锋！

Date Time

16/10/26 09:09

Author

Category

BZOJ

Tags

, ,
Leave a Reply

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
 
 
 
/* ***********************************************
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;
}
 
 
 
 

 

说点什么

您将是第一位评论人！

提醒
wpDiscuz