Description

有一个大小为 \(n\) 的可重集 \(S\), 小奇每次操作可以加入一个数 \(a + b (a, b \in S)\), 求 \(k\) 次操作后它可获得的 \(S\) 的和的最大值. (数据保证这个值为非负数)

Input

第一行有两个整数 \(n, k\) 表示初始元素数量和操作数, 第二行包含 \(n\) 个整数表示初始时 可重集的元素.

Output

输出一个整数, 表示和的最大值. 答案对 10000007 取模.

Sample Input

2 2
3 6

Sample Output

33

Data Range

对于 100% 的数据, 有 \(n \leq 10^5, k \leq 10^9, |a_i| \leq 10^5\)

Explanation

为什么黄学长出的题他自己没写题解呢 (雾)

看一眼就是贪心, 因为不弄两个最大的弄谁 (证明太智障, 此处不写)

然后考虑到第二大的可能是负数, 把他补成正数就可以了

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const lli infinit = 0x007f7f7f7f7f7f7fll;
const int modr = 10000007;

struct matrix
{
    lli arr[4][4];
    matrix(void) {
        memset(arr, 0, sizeof(arr));
        return ; }
    matrix(int _11, int _12, int _13, int _21, int _22, int _23, int _31, int _32, int _33) {
        arr[1][1] = _11, arr[1][2] = _12, arr[1][3] = _13;
        arr[2][1] = _21, arr[2][2] = _22, arr[2][3] = _23;
        arr[3][1] = _31, arr[3][2] = _32, arr[3][3] = _33;
        return ; }
};
matrix operator * (matrix a, matrix b)
{
    matrix c;
    rep(i, 1, 3) rep(j, 1, 3) rep(k, 1, 3)
        c.arr[i][j] = (c.arr[i][j] + a.arr[i][k] * b.arr[k][j] % modr) % modr;
    return c;
}
matrix operator ^ (matrix a, lli b)
{
    matrix res;
    rep(i, 1, 3) res.arr[i][i] = 1;
    for (int i = b; i > 0; i >>= 1, a = a * a)
        if (i & 1)
            res = res * a;
    return res;
}

int n, K;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &K);
    lli mx1 = -infinit, // The maximum
        mx2 = -infinit; // Second maximum
    lli S = 0;
    // Hope you guranteed n >= 2
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        if (x > mx1)
            mx2 = mx1, mx1 = x;
        else if (x >= mx2)
            mx2 = x;
        S = (S + x) % modr;
    }
    // Making second largest number non-negative
    while (mx2 < 0 && K > 0) {
        mx2 = (mx1 + mx2) % modr;
        S = mx2 + S % modr;
        K -= 1;
    }
    // Creating matrix
    matrix a(
        1,  1,  0,
        1,  0,  0,
        1,  1,  1);
    matrix res(
        mx1, 0, 0,
        mx2, 0, 0,
        S,   0, 0);
    // Evolving result
    res = (a ^ K) * res;
    lli f_res = (res.arr[3][1] + modr) % modr;
    printf("%lld\n", f_res);
    return 0;
}