概要

\(N\) 個の株式銘柄があり、それぞれの評価額が与えられます。合計 \(K\) 回の投資チャンスを使って、どれか一つの銘柄の評価額を2倍にできます。最終的な評価額の合計の最大値を求める問題です。

考察

まず、投資チャンスは評価額を2倍にする操作であり、これは指数的に増加します。したがって、できるだけ評価額の高い銘柄に対して操作を行うのが最も効果的です。

例えば、銘柄A（評価額100）と銘柄B（評価額50）があり、投資チャンスが2回ある場合、
- Aに2回使うと：100 → 200 → 400、合計は400＋50＝450
- Bに2回使うと：50 → 100 → 200、合計は200＋100＝300
となり、大きい方に集中させるのが最適です。

このように、複数回の操作は最も評価額の高い銘柄に全部使うのが最適となります。

したがって、入力された評価額を降順にソートし、最も大きい値に \(2^K\) をかけ、それ以外の銘柄の評価額の和を足し合わせればよいです。

また、\(K\) が非常に大きいため（最大 \(10^{18}\)）、単純に2をK回掛けることはできません。代わりに、繰り返し二乗法によるべき乗（\(2^K \bmod (10^9+7)\)）を使う必要があります。

アルゴリズム

1. 各銘柄の評価額 \(L_i\) を降順にソートします。
2. 最も大きい評価額 \(L_0\) に対して、\(2^K\) を繰り返し二乗法で求めます。
3. その他の銘柄の評価額の合計を求めます。
4. 最終的な答えは： $\( (L_0 \times 2^K + \sum_{i=1}^{N-1} L_i) \bmod (10^9 + 7) \)$

計算量

• 時間計算量: \(O(N \log N)\) （ソートが支配的）
• 空間計算量: \(O(1)\) （入力を除けば定数）

実装のポイント

• Pythonでは pow(base, exp, mod) を使うことで、繰り返し二乗法による高速なべき乗計算が可能です。
• 最終結果を \(10^9 + 7\) で割った余りとして出力することを忘れないようにしましょう。
• ソート後に最も大きい要素に操作を集中させることを意識しましょう。

## ソースコード

```python
MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    L = list(map(int, data[2:]))

    # Lを降順にソート
    L.sort(reverse=True)

    # 最大の要素に2^Kをかけるのが最適
    max_val = L[0]
    rest_sum = sum(L[1:]) % MOD if N > 1 else 0

    # powで2^K mod MODを高速計算
    power_of_2 = pow(2, K, MOD)
    
    # (max_val * 2^K) + sum of other elements
    max_contribution = (max_val % MOD) * power_of_2 % MOD
    result = (max_contribution + rest_sum) % MOD
    
    print(result)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。