概要

ブロック塔を順番に積み上げていく際、左から見たときに「見える塔」が常に \(K\) 本以上であるという条件を満たしながら、すべての塔を目標の高さまで積み上げる手順の総数を求める問題です。

考察

1手目の条件に注目する

まず、1ステップ目に何が起こるかを考えます。1手目では1つの塔に1個のブロックを載せるため、直後の状態は「ある1つの塔の高さが \(1\)、それ以外の塔の高さが \(0\)」となります。 左から見たときに塔が見える条件は、「高さが \(1\) 以上であり、かつ左にあるすべての塔の高さより真に大きい」ことです。1手目の直後では、高さが \(1\) の塔は1本しかなく、それより左の塔はすべて高さ \(0\) です。したがって、見える塔は必ず \(1\) 本のみになります。 問題文の見栄え条件は「各ステップの直後において」とあるため、1手目の直後にも \(K\) 本以上の塔が見える必要があります。 もし \(K \geq 2\) であれば、1手目の時点で条件を満たすことが不可能であるため、答えは \(0\) になります。

\(K = 1\) の場合の見栄え条件

\(K = 1\) の場合、常に「見える塔が \(1\) 本以上」という条件を満たす必要があります。 どのタイミングでも、高さが \(1\) 以上の塔が少なくとも1本存在する限り、最も高く、かつ最も左にある塔が「見える」と判定されます。ブロックを積む作業を1回以上行っている限り高さ \(1\) 以上の塔は存在するため、作業途中でこの条件が破られることはありません。 つまり、\(K = 1\) の場合、どのような順番でブロックを積み上げても見栄え条件を常に満たすことになります。

手順の総数の計算

すべての塔を目標の高さまで積み上げるには、合計で \(S = \sum_{i=1}^{N} H_i\) 個のブロックを積む必要があります。 各ブロックは区別がつきませんが、「どの塔に対してブロックを置くか」という操作の順番が重要になります。各塔 \(i\) には最終的に \(H_i\) 個のブロックが置かれます。 これは、\(S\) 個の枠に対して、塔 \(1\) 用のブロックを \(H_1\) 個、塔 \(2\) 用のブロックを \(H_2\) 個、……と配置する順列の数と同じです。 したがって、手順の総数は多重集合の順列となり、\(\frac{S!}{H_1! H_2! \cdots H_N!}\) になります。

アルゴリズム

1. 入力を受け取り、すべての塔の目標の高さの合計 \(S\) を計算します。
2. もし \(K \geq 2\) であれば、条件を満たす手順が存在しないため \(0\) を出力して終了します。
3. \(K = 1\) の場合、以下の計算を行います。
   • \(S!\) を \(10^9 + 7\) で割った余りを求めるため、前計算で \(0\) から \(S\) までの階乗 fact を求めます。
   • 割り算の代わりに逆元を掛け算するため、\(S!\) の逆元 invfact[S] をべき乗の性質（フェルマーの小定理）を用いて求めます。
   • これを用いて、\(S-1\) から \(0\) までの階乗の逆元 invfact を漸的に求めます。
   • 答えは fact[S] * invfact[H_1] * invfact[H_2] * ... * invfact[H_N] を \(10^9 + 7\) で割った余りとして計算し、出力します。

計算量

• 時間計算量: \(O(S + N)\) 階乗とその逆元の前計算に \(O(S)\)、各塔の高さの入力と答えの計算に \(O(N)\) かかります。
• 空間計算量: \(O(S + N)\) 階乗とその逆元を保存する配列に \(O(S)\)、高さを保存する配列に \(O(N)\) の空間を必要とします。

実装のポイント

• \(S\) が最大で \(10^6\) になるため、階乗と逆元の配列を動的確保する際に long long 型を使用するとメモリ制限を超える可能性があります。本問題の制約下では十分に収まりますが、メモリに余裕を持たせるために配列は適切な型を選択することが重要です。

• 剰余を取る計算（% MOD）は掛け算のたびに行い、オーバーフローを防ぐようにします。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1'000'000'007;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

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

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

    // 最初の1手目では、どうしても1本の塔しか高さ1にならず、見える塔は1本のみ。
    // したがって、K >= 2 ならば1手目の直後で条件を満たさず、不可能。
    if (K >= 2) {
        cout << 0 << "\n";
        return 0;
    }

    // K == 1 の場合
    // ブロックを1つでも積めば、その時点で高さ1以上の塔が存在し、
    // 常に少なくとも1本（最も高く、かつ最も左にある塔）は見えるため、
    // 任意の積み上げ順序で条件を満たす。
    // よって、多重集合の順列の総数を求めればよい。

    vector<long long> fact(S + 1);
    vector<long long> invfact(S + 1);
    fact[0] = 1;
    for (int i = 1; i <= S; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    invfact[S] = 1;
    long long p = fact[S];
    long long e = MOD - 2;
    long long cur = 1;
    while (e > 0) {
        if (e % 2 == 1) cur = cur * p % MOD;
        p = p * p % MOD;
        e /= 2;
    }
    invfact[S] = cur;
    for (int i = S - 1; i >= 0; i--) {
        invfact[i] = invfact[i + 1] * (i + 1) % MOD;
    }

    long long ans = fact[S];
    for (int i = 0; i < N; i++) {
        ans = ans * invfact[H[i]] % MOD;
    }

    cout << ans << "\n";
    return 0;
}

---

この解説は or-glm5.2-high によって生成されました。