【BZOJ4547】Hdu5171 小奇的集合

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

题解：首先贪心的想，我们肯定是选取最大值和次大值，然后进行如下讨论：

如果最大值和次大值都>=0，则我们每次用最大值+次大值得到新的最大值，由于K是10^9，所以用矩乘加速即可。

如果只有次大值<0，那么我们先不断用最大值+次大值得到新的次大值，直到次大值>=0，然后同上。

如果最大值<0，那么不断将最大值和次大值相加即可。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const ll P=10000007;

int n;

ll m,a1,a2,sum;

struct M

{

	ll a[5][5];

	M () {memset(a,0,sizeof(a));}

	ll * operator [] (int b) {return a[b];}

	M operator * (M b)

	{

		M c;

		int i,j,k;

		for(i=1;i<=3;i++)	for(j=1;j<=3;j++)	for(k=1;k<=3;k++)	c[i][j]=(c[i][j]+a[i][k]*b[k][j])%P;

		return c;

	}

}ans,tr;

void pm(ll y)

{

	while(y)

	{

		if(y&1)	ans=ans*tr;

		tr=tr*tr,y>>=1;

	}

}

int main()

{

	scanf("%d%lld",&n,&m);

	int i;

	ll a;

	a1=a2=-1<<30;

	for(i=1;i<=n;i++)

	{

		scanf("%lld",&a),sum=(sum+a+P)%P;

		if(a>a1)	a2=a1,a1=a;

		else	a2=max(a2,a);

	}

	if(a1<0)

	{

		printf("%lld",(sum+(a1+a2+P+P)*m)%P);

		return 0;

	}

	while(a2<0&&m)	a2=a1+a2,sum=(sum+a2)%P,m--;

	if(!m)

	{

		printf("%lld",sum);

		return 0;

	}

	tr[1][1]=tr[1][2]=tr[1][3]=tr[2][1]=tr[2][3]=tr[3][3]=1;

	ans[1][1]=a1,ans[1][2]=a2,ans[1][3]=sum;

	pm(m);

	printf("%lld",ans[1][3]);

	return 0;

}

小奇