概要

各操作で「ある銘柄の評価額を 2 倍」にできるとき、\(K\) 回後の合計評価額を最大化し、その値を \(10^9+7\) で割った余りを求めます。

考察

1 回の操作で増える合計額（増分）に注目します。

• ある銘柄の現在値が \(x\) のとき、2 倍にすると合計は \(x\) だけ増える（\(x \to 2x\) なので増分は \(2x-x=x\)）。
• つまり「どの銘柄を選ぶべきか」は、その時点で 現在値が最大の銘柄を選ぶのが最も得です。

さらに重要なのは、一度最大の銘柄を選んで 2 倍にすると、その銘柄はより大きくなり、次の操作で得られる増分もさらに大きくなる点です。
最大値を \(m=\max(L_i)\) とすると、

• 最大銘柄を選ぶと増分は \(m\)、その後は \(2m,4m,\dots\) と増分が増えていく。
• 一方、最大以外の銘柄を選んでも増分は高々その銘柄の現在値で、初回時点でも \(m\) 以下、しかも最大銘柄を成長させた場合の増分には追いつけません。

したがって、最適戦略は 常に最初の最大値の銘柄を \(K\) 回連続で 2 倍することです（他を選ぶ操作があれば、その操作を最大銘柄への操作に置き換えると合計が減らない／増える、という交換の議論で正当化できます）。

このとき最終的な合計は - 最大銘柄以外の合計は変化しない - 最大銘柄 \(m\) は \(m \cdot 2^K\) になる

なので [ \text{答え}=(\sum_{i=1}^N Li - m) + m\cdot 2^K = \sum{i=1}^N L_i + m(2^K-1) ] となります。

素朴に \(K\) 回シミュレーションすると \(K\le 10^{18}\) で不可能（TLE）なので、\(2^K\) は繰り返し二乗法（Python の pow(2, K, MOD)）で高速に計算します。

アルゴリズム

1. \(L\) の最大値 \(m=\max(L)\) を求める。
2. \(\text{sum}=\sum L_i\) を求める。
3. \(p = 2^K \bmod MOD\) を pow(2, K, MOD) で計算する。
4. 公式 [ \text{ans} = \text{sum} + m(2^K-1) ] を MOD 上で計算して出力する。 具体的には [ \text{ans} = (\text{sum}\bmod MOD + (m\bmod MOD)\cdot((p-1)\bmod MOD))\bmod MOD ]

（例）\(L=[3,5,2], K=2\)
最大は \(m=5\)。最大銘柄を 2 回倍増すると \(5\to10\to20\)、合計は \(3+20+2=25\)。
式でも \(\sum L=10\)、\(10+5(4-1)=25\)。

計算量

• 時間計算量: \(O(N)\)（最大値と総和の計算）＋ \(O(\log K)\)（べき乗）だが支配的には \(O(N)\)
• 空間計算量: \(O(1)\)（入力配列以外）

実装のポイント

• \(K\) が非常に大きいので、\(2^K\) は必ず pow(2, K, MOD) のように mod 付き高速べき乗を使う。

• 答えは [ \sum L_i + m(2^K-1) ] なので、(pow2 - 1) % MOD のように 負にならない形で mod を取ると安全です（今回 pow2 は必ず \(1\) 以上ですが、一般に癖として有用）。

  ソースコード

import sys

MOD = 10**9 + 7

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    L = list(map(int, input().split()))
    m = max(L)
    sum_mod = sum(L) % MOD
    pow2 = pow(2, K, MOD)
    ans = (sum_mod + (m % MOD) * ((pow2 - 1) % MOD)) % MOD
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。