bzoj 4547 小奇的集合

Posted on | Views:

贪心 + 矩阵快速幂.

  • 显然可以贪心,每次取最大的两个数加起来.答案为初始所有元素之和加上每次操作加入的数.
  • 记初始时最大数为 $a$ ,次大数为 $b$ ,因为题目保证答案非负,所以 $a,b$ 不可能都为负.
  • 若 $a,b$ 都非负,那么加入的数就是一个类斐波那契数列,用矩阵快速幂加速计算就可以了.
  • 若 $a>0$ , $b<0$ ,那么就先算出最少要加几次能使得有两个非负数.只要 $k$ 不为 $0$ ,又保证最终答案为非负,那么一定能在 $k$ 次之内得到两个非负数.
  • 这部分贡献可以直接算出,然后再对剩余次数计算类斐波那契数列部分的贡献即可.

记得答案 $+$ 模数后再输出.

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int inf=0x7fffffff;
const int P=1e7+7;
const int inv2=(P+1)>>1;
inline int add(int a,int b)
{
	return (a + b) % P;
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
struct Matrix
{
	int A[3][3];
	Matrix(){memset(A,0,sizeof A);}
	Matrix operator * (const Matrix &rhs) const
	{
		Matrix res;
		for(int k=0;k<3;++k)
			for(int i=0;i<3;++i)
				for(int j=0;j<3;++j)
					res.A[i][j]=add(res.A[i][j],mul(A[i][k],rhs.A[k][j]));
		return res;
	}
};
Matrix fpow(Matrix a,int b)
{
	Matrix res;
	for(int i=0;i<3;++i)
		res.A[i][i]=1;
	while(b)
	{
		if(b&1)
			res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
int calc(int a,int b,int k)
{
	assert(k>=0);
	Matrix trans,st;
	trans.A[0][0]=trans.A[0][1]=1;
	trans.A[1][0]=1;
	trans.A[2][0]=trans.A[2][1]=trans.A[2][2]=1;
	st.A[0][0]=a;
	st.A[1][0]=b;
	st=fpow(trans,k)*st;
	return st.A[2][0];
}
int main()
{
	int n=read(),k=read(),ans=0;
	int a=-inf,b=-inf;
	while(n--)
	{
		int x=read();
		ans=add(ans,x);
		if(x>a)
			b=a,a=x;
		else if(x>b)
			b=x;
	}
	if(a>=0 && b>=0)
		ans=add(ans,calc(a,b,k));
	else
	{
		int tmp=(-b+a-1)/a;
		ans=add(ans,mul(tmp,b));
		ans=add(ans,mul(a,mul(inv2,mul(tmp+1,tmp))));
		k-=tmp;
		b=tmp*a+b;
		if(b>a)
			swap(a,b);
		ans=add(ans,calc(a,b,k));
	}
	cout<<add(ans,P)<<endl;
	return 0;
}