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
3 6
Sample Output
33
显然可以把原数组排序，新元素就是最后2项之和
但是原题只保证答案是非负数，所以会有小于0的情况
而且不会出现最大和次大都是负数，最多就是最大为正，次大为负
相加直到两个数都为正数
然后就可以矩阵快速幂
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long lol;
lol Mod=1e7+;
struct Matrix
{
lol a[][];
} ans,Mat;
lol n,a[],k,sum;
Matrix operator *(const Matrix &a,const Matrix &b)
{
lol i,j,l;
Matrix res;
memset(res.a,,sizeof(res.a));
for (i=; i<=; i++)
{
for (j=; j<=; j++)
{
for (l=; l<=; l++)
{
res.a[i][j]+=a.a[i][l]*b.a[l][j]%Mod;
res.a[i][j]=(res.a[i][j]%Mod+Mod)%Mod;
}
}
}
return res;
}
Matrix qpow(lol y)
{
lol i;
Matrix res;
memset(res.a,,sizeof(res.a));
for (i=; i<=; i++)
res.a[i][i]=;
while (y)
{
if (y&) res=res*Mat;
Mat=Mat*Mat;
y>>=;
}
return res;
}
int main()
{
lol i;
cin>>n>>k;
for (i=; i<=n; i++)
{
scanf("%lld",&a[i]);
sum=(sum+a[i])%Mod;
}
sort(a+,a+n+);
if (k==)
{
cout<<sum;
return ;
}
if (a[n-]<)
{
a[n+]=(a[n]+a[n-]);
n++;
k--;
sum=(sum+a[n]%Mod)%Mod;
swap(a[n],a[n-]);
}
ans.a[][]=;
ans.a[][]=(a[n]+Mod)%Mod;
ans.a[][]=(a[n-]+Mod)%Mod;
Mat.a[][]=;
Mat.a[][]=;
Mat.a[][]=;
Mat.a[][]=;
Mat.a[][]=;
Mat.a[][]=;
ans=ans*qpow(k);
cout<<((sum+ans.a[][])%Mod+Mod)%Mod;
}