[HDU517] 小奇的集合

题目链接

显然有贪心每次选择最大的两个数来做。

于是暴力地把最大的两个数调整到非负（暴力次数不超过1e5），接下来使用矩阵乘法即可。

\[\begin{pmatrix}
B'\\S'\\T'
\end{pmatrix}
=
\begin{pmatrix}
1&1&0\\
1&0&0\\
1&1&1
\end{pmatrix}
\begin{pmatrix}
B\\S\\T
\end{pmatrix}
\]

#include <bits/stdc++.h>

using namespace std;

const int mod=1e7+7;

struct Node {

	int a[3][3];

	int *operator[](const int&d) {return a[d];}

	const int *operator[](const int&d) const{return a[d];}

	Node operator*(const Node&b) const{

		Node c;

		memset(&c,0,sizeof c);

		for(int i=0; i<3; ++i)

		for(int k=0; k<3; ++k) if(a[i][k])

		for(int j=0; j<3; ++j)

			c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j]%mod)%mod;

		return c;

	}

	Node pow(int y) {

		Node c,x=*this;

		for(int i=0; i<3; ++i)

		for(int j=0; j<3; ++j) c[i][j]=(i==j);

		for(; y; y>>=1,x=x*x) if(y&1) c=c*x;

		return c;

	}

} G,M;

int n,k,sum,a[200010];

int main() {

	scanf("%d%d",&n,&k);

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

		scanf("%d",a+i);

		sum=(sum+a[i]+mod)%mod;

	}

	sort(a+1,a+n+1);

	while(a[n-1]<0&&k>0) {

		a[n+1]=(a[n]+a[n-1]); n++; k--;

		sum=(sum+a[n]+mod)%mod;

		swap(a[n],a[n-1]);

	}

	if(k==0) {

		printf("%d\n",sum);

		return 0;

	}

	M[0][0]=a[n];

	M[1][0]=a[n-1];

	M[2][0]=sum;

	G[0][0]=G[0][1]=1;

	G[1][0]=1;

	G[2][0]=G[2][1]=G[2][2]=1;

	Node ans=G.pow(k)*M;

	printf("%d\n",ans[2][0]);

	return 0;

}