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

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

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;

}

作者： CrazyKK

ex-ACMer@hust，stackoverflow-engineer@sensetime 查看CrazyKK的所有文章

4547: Hdu5171 小奇的集合

Description

Input

Output

Sample Input

Sample Output

HINT

Source

作者： CrazyKK

说点什么