概要

この問題は、与えられた \(N\) 個の要素（果樹の初期成長度 \(A_i\)）の総和をちょうど \(K\) だけ増やしたときに、すべての要素の積（収穫量）を最大化する問題です。

積を最大化するためには、「値の小さい要素を優先的に大きくして、全体の値をできるだけ均等に近づける」のが最適です。この性質を利用し、二分探索と高速なべき乗計算を組み合わせることで、膨大な \(K\) に対しても高速に最適な配分を求めることができます。

---

考察

1. 積を最大化するための最適な戦略

2つの変数 \(x, y\) があり、その和 \(x + y = S\)（一定）であるとき、積 \(x \times y\) は \(x\) と \(y\) の差が小さいほど大きくなります。 例えば、和が \(10\) のとき： - \(2 \times 8 = 16\) - \(5 \times 5 = 25\) （こちらの方が大きい）

この性質は \(N\) 個の変数になっても同様です。したがって、肥料を配分する際は「現在最も成長度が低い果樹に優先的に肥料を与える」という貪欲な選択が最適になります。

2. 素朴なアプローチとその限界

「最も小さい要素に肥料を \(1\) 袋与える」という操作を \(K\) 回繰り返せば、最適な配分をシミュレーションできます。 しかし、今回の制約では \(K \le 10^{18}\) と非常に大きいため、1ずつシミュレーションを行うと実行時間制限（TLE）になってしまいます。

3. 二分探索による解決

そこで、視点を変えて「すべての果樹の最終的な成長度を \(X\) 以上にできるか？」という判定問題を考えます。

成長度が \(X\) 未満の果樹をすべて \(X\) にするために必要な肥料の総数は、 $\( \sum_{i=1}^{N} \max(0, X - A_i) \)\( となります。これが \)K\( 以下であれば、すべての果樹の成長度を \)X$ 以上にすることが可能です。

この必要な肥料の総数は \(X\) に対して単調増加（\(X\) が大きくなるほど必要な肥料も増える）するため、二分探索（Binary Search）を用いて「すべての果樹を \(X\) 以上にできる最大の \(X\)」を高速に求めることができます。

4. 余った肥料の分配

最大の \(X\) を求めた後、まだ肥料が余っている場合があります。 余った肥料の数を \(R\) とすると、この \(R\) 袋の肥料は、成長度が \(X\) になった果樹のうちの \(R\) 本に \(1\) 袋ずつ配分するのが最適です（これにより、それらの果樹の成長度は \(X + 1\) になります）。

---

アルゴリズム

1. 二分探索で目標値 \(X\) を決定する

   • 探索範囲を low = 1, high = 2 * 10^18 とします。
   • 中央値 mid について、すべての \(A_i\) を mid 以上にするために必要な肥料の総和を計算します。
   • 総和が \(K\) 以下であれば、さらに大きい値にできる可能性があるので low = mid + 1 とし、そうでなければ high = mid - 1 とします。

2. 余りの肥料 \(R\) を計算する

   • 求まった最大の \(X\)（コード中では ans_X）に対して、すべての果樹を \(X\) 以上にするために実際に消費する肥料の総数 \(S\) を計算します。
   • 残りの肥料は \(R = K - S\) となります。

3. 最終的な積（答え）を計算する

   • 元々の成長度が \(X\) より大きかった果樹（\(A_i > X\)）は、肥料を与えられずそのまま \(A_i\) となります。
   • 元々の成長度が \(X\) 以下だった果樹（\(A_i \le X\)）は、すべて一旦成長度が \(X\) になります。
   • そのうち \(R\) 本の果樹は、余った肥料によって成長度が \(X + 1\) になり、残りの果樹は \(X\) のままです。
   • これらの値をすべて掛け合わせたものを \(10^9 + 7\) で割った余りを求めます。同じ値を何度も掛ける部分は、繰り返し二乗法を用いて高速に計算します。

---

計算量

• 時間計算量: \(O(N \log(\max A_i + K))\)

  • 二分探索の判定1回につき \(O(N)\) のループが走ります。二分探索の回数は最大でも \(\log_2(2 \times 10^{18}) \approx 61\) 回であるため、この部分は十分高速です。
  • 最後の積の計算は \(O(N + \log N)\) です。
  • 全体として、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(N)\)

  • 各果樹の初期成長度 \(A_i\) を格納する配列のサイズ分のみメモリを消費します。

---

実装のポイント

• オーバーフローの防止 二分探索の判定の際、必要な肥料の総和を単純に足していくと、一時的に long long の最大値を超える（オーバーフローする）可能性があります。 コード内では、sum + (mid - A[i]) > K という条件を mid - A[i] > K - sum と移項して比較することで、安全にオーバーフローを防止しています。

• 繰り返し二乗法による高速なべき乗計算 同じ値 \(X\) や \(X+1\) を大量に掛け合わせる必要があるため、power 関数（繰り返し二乗法）を実装して \(O(\log N)\) で計算できるようにしています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to calculate (base^exp) % mod
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    if (base < 0) base += mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // Binary search to find the maximum possible minimum growth level X
    long long low = 1;
    long long high = 2000000000000000000LL; // 2 * 10^18, safe upper bound
    long long ans_X = 1;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        long long sum = 0;
        bool ok = true;
        for (int i = 0; i < N; ++i) {
            if (mid > A[i]) {
                // Safe overflow check for sum + (mid - A[i]) > K
                if (mid - A[i] > K - sum) {
                    ok = false;
                    break;
                }
                sum += mid - A[i];
            }
        }
        if (ok) {
            ans_X = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    // Calculate the exact amount of fertilizer used to bring all elements to at least ans_X
    long long S = 0;
    for (int i = 0; i < N; ++i) {
        if (ans_X > A[i]) {
            S += ans_X - A[i];
        }
    }
    long long R = K - S; // Remaining fertilizer to distribute

    long long MOD = 1000000007;
    long long ans = 1;
    long long count_le = 0;

    // Separate elements that are strictly greater than ans_X
    for (int i = 0; i < N; ++i) {
        if (A[i] > ans_X) {
            ans = (ans * (A[i] % MOD)) % MOD;
        } else {
            count_le++;
        }
    }

    // Out of count_le elements that became ans_X, R of them will be incremented to ans_X + 1
    long long term1 = power(ans_X, count_le - R, MOD);
    long long term2 = power(ans_X + 1, R, MOD);

    ans = (ans * term1) % MOD;
    ans = (ans * term2) % MOD;

    cout << ans << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。