概要

各操作で「選んだ銘柄の価値を2倍」にできるとき、最終的な合計価値を最大化するにはどの銘柄を選ぶべきかを考え、最大値を \(10^9+7\) で求めます。

考察

1回の操作が合計に与える増分

ある時点で価値が \(x\) の銘柄を2倍にすると、その銘柄は \(x \to 2x\) になるので、合計は \(+x\) だけ増えます（増えた分はちょうど元の値 \(x\)）。

つまり、各回の操作で得られる利益（合計の増分）は「その時点で選んだ銘柄の価値」です。

では毎回どれを選ぶべきか？

その回の増分は選んだ銘柄の価値に等しいので、その時点で一番価値が大きい銘柄を選べば、その回の増分が最大になります。

さらに重要なのは、最大の銘柄を2倍にすると次回以降もより大きくなり、以後の増分も大きくできることです。直感的には、

• 大きい銘柄を育てるほど、次の操作で得られる増分も大きくなる
  
• 小さい銘柄を2倍にしても、その回の増分が小さい上に、最大銘柄を育てる機会を失う

という理由で、操作はすべて（初期値が）最大の銘柄に集中させるのが最適になります。

具体例

\(S=[3,5,4],\ K=2\) のとき、最大は \(5\)。

• 最大（5）を2回選ぶ：
  1回目の増分 \(+5\)、2回目の増分 \(+10\)、合計増分 \(15\)
• 5を1回、4を1回選ぶ：
  増分 \(+5\) と \(+4\) で合計増分 \(9\)（小さい）

このように、最大銘柄を育て続けるのが得です。

素朴な方法がダメな理由

\(K\) は最大で \(10^{18}\) なので、 - 「\(K\) 回シミュレーションする」→ \(O(K)\) で到底間に合いません。 - 値も指数的に増えるので通常の整数では非常に大きくなります。

よって、数式で一気に求め、かつ剰余で計算する必要があります。

アルゴリズム

最大の銘柄の初期値を \(m=\max(S)\)、初期合計を \(A=\sum S_i\) とします。

最大の銘柄だけを \(K\) 回2倍にすると、その銘柄の値は - \(m \to 2^K m\)

合計は - 最終合計 \(= (A - m) + 2^K m = A + m(2^K - 1)\)

よって答えは - \(\left(\sum S_i + \max(S)\cdot(2^K-1)\right) \bmod (10^9+7)\)

\(2^K \bmod MOD\) は高速べき乗（Python の pow(2, K, MOD)）で計算します。

計算量

• 時間計算量: \(O(N)\)（最大値と合計を求めるだけ）
• 空間計算量: \(O(1)\)（入力配列を除く）

実装のポイント

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

• \(2^K-1\) が負にならないように、(p2 - 1) % MOD として扱う（コードではこれをしている）。

• 合計も都度 % MOD を取ってオーバーフローを避ける（Pythonでも巨大数は扱えますが、計算が重くなるのを避けられます）。

  ソースコード

import sys

MOD = 10**9 + 7

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    S = data[2:2+N]

    mx = max(S)
    sm = sum(S) % MOD
    p2 = pow(2, K, MOD)

    ans = (sm + (mx % MOD) * ((p2 - 1) % MOD)) % MOD
    print(ans)

if __name__ == "__main__":
    main()

---

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