#P4547. Hdu5171 小奇的集合

    ID: 3668 传统题 1000ms 256MiB 尝试: 816 已通过: 256 难度: 6 上传者: 标签>CF1900普及+/提高-支配关系等差数列求和增广状态矩阵矩阵快速幂矩阵优化Dp

Hdu5171 小奇的集合

题目描述

有一个大小为 nn 的可重集 SS,小奇每次操作可以加入一个数 a+ba+b(a,ba,b 均属于 SS),求 kk 次操作后它可获得的 SS 的和的最大值。(数据保证这个值为非负数)

输入格式

第一行有两个整数 n,kn,k,表示初始元素数量和操作数。

第二行包含 nn 个整数,表示初始时可重集的元素。

输出格式

输出一个整数,表示和的最大值。答案对 107+710^7+7 取模。

样例输入

2 2
3 6

样例输出

33

数据规模与约定

对于 100%100\% 的数据,有 n≤105n \le 10^5,k≤109k\le10^9,∣ai∣≤105|a_i|\le10^5。

题目来源

By Hzwer