概要

ブロックを1個ずつ積み上げていく中で、常に「左端から見える塔」が \(K\) 本以上であるような手順の総数を求める問題です。一見複雑な条件に見えますが、最初の1ステップ目に注目することで、問題が非常にシンプルな数え上げに帰着されます。

考察

1. 「見える塔」の定義と1ステップ目の状態

\(i\) 番目の塔が見えるためには、現在のその塔の高さ \(h_i\) が \(1\) 以上であり、かつそれより左にあるすべての塔よりも高くなければなりません。

ここで、最初のステップ（ブロックを1個だけ置いた直後）を考えてみましょう。 このとき、すべての塔の高さの合計は \(1\) です。つまり、高さが \(1\) の塔が \(1\) つだけ存在し、他のすべての塔の高さは \(0\) です。

この状態で「見える塔」は、ブロックが置かれたその1本の塔のみ（\(1\) 本）となります。どれだけ工夫してブロックを置いても、1ステップ目の直後に見える塔を \(2\) 本以上にすることは不可能です。

2. \(K \ge 2\) の場合

1ステップ目の直後にはどう頑張っても \(1\) 本の塔しか見えません。 したがって、 \(K \ge 2\) の場合は、最初の1歩目で必ず「見える塔が \(K\) 本以上」という見栄え条件を満たせなくなります。 よって、 \(K \ge 2\) のときの答えは常に \(0\) 通り です。

3. \(K = 1\) の場合

条件は「常に \(1\) 本以上の塔が見えること」になります。 ブロックが少なくとも \(1\) 個置かれているとき、高さが \(1\) 以上の塔が少なくとも \(1\) つ存在します。 左から順に塔を見ていくと、最初に現れる「高さが \(1\) 以上の塔」は、それより左に高さ \(1\) 以上の塔がないため、必ず「見える塔」の条件を満たします。

つまり、ブロックが \(1\) 個以上ある限り、見える塔は常に \(1\) 本以上存在します。 したがって、 \(K = 1\) の場合は、どのような順番でブロックを積み上げても常に条件を満たします。

4. 手順の数え上げ

\(K = 1\) のとき、問題は単に「 \(i\) 番目の塔に \(H_i\) 個のブロックを積み上げる手順の総数」を求める問題になります。 全体のブロックの総数を \(S = \sum_{i=1}^{N} H_i\) とします。 \(S\) 回のステップのうち、 \(i\) 番目の塔にブロックを置くステップを \(H_i\) 回選ぶ方法の数に等しいため、これは同じものを含む順列（多項係数）として以下のように計算できます。

\[ \frac{S!}{H_1! H_2! \cdots H_N!} \pmod{10^9+7} \]

アルゴリズム

1. \(K \ge 2\) の場合は、即座に 0 を出力して終了します。
2. \(K = 1\) の場合：
   • \(H_i\) の総和 \(S = \sum H_i\) を計算します。
   • \(0\) から \(S\) までの階乗 \(x! \pmod{10^9+7}\) を前計算します。
   • 分子の \(S!\) に対し、各分母の \(H_i!\) の逆元を掛け合わせることで、多項係数を計算します。逆元の計算にはフェルマーの小定理（ \(a^{-1} \equiv a^{MOD-2} \pmod{MOD}\) ）と繰り返し二乗法を使用します。

計算量

• 時間計算量: \(O(S + N \log(\text{MOD}))\)
  • \(S = \sum H_i \le 10^6\) です。階乗テーブルの作成に \(O(S)\) 、各 \(H_i!\) の逆元計算に \(O(\log(\text{MOD}))\) かかります。制約より十分高速に動作します。
• 空間計算量: \(O(S + N)\)
  • 階乗を保持する配列に \(O(S)\) 、入力の保持に \(O(N)\) のメモリを使用します。

実装のポイント

• 逆元の計算: \(10^9+7\) は素数であるため、フェルマーの小定理を用いた繰り返し二乗法による高速なべき乗計算で逆元を求めることができます。

• 高速入出力: \(N\) や \(S\) が最大 \(10^6\) 規模になるため、C++では cin.tie(NULL) や ios_base::sync_with_stdio(false) を用いて入出力を高速化しておくと安全です。

  ソースコード

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

const int MOD = 1000000007;

// 高速なべき乗計算
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// モジュラ逆数
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

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

    // 各ステップの直後において見える塔が K 本以上必要。
    // 1ステップ目の直後はブロックが1個しかないため、見える塔は高々1本。
    // したがって、K >= 2 の場合は1ステップ目の直後で必ず条件を満たさなくなる。
    if (K >= 2) {
        cout << 0 << "\n";
        return 0;
    }

    // K == 1 の場合、常に1本以上の塔が見えればよい。
    // 各ステップの直後、高さ1以上の塔は必ず1つ以上存在するため、常に条件を満たす。
    // したがって、求める数はすべてのブロックを置く手順の総数。
    // 手順の総数は、多項係数 (sum_H)! / (H_1! * H_2! * ... * H_N!) % MOD となる。
    vector<long long> fact(sum_H + 1, 1);
    for (int i = 2; i <= sum_H; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }

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

    cout << ans << "\n";

    return 0;
}

---

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