Overview

This problem asks us to find the total number of ways to stack blocks one by one such that the number of “towers visible from the left” is always at least \(K\). Although the condition seems complex at first glance, focusing on the very first step reduces the problem to a very simple counting problem.

Analysis

1. Definition of “Visible Towers” and the State at Step 1

For the \(i\)-th tower to be visible, its current height \(h_i\) must be at least \(1\), and it must be strictly taller than all towers to its left.

Here, let us consider the first step (immediately after placing only one block). At this moment, the sum of the heights of all towers is \(1\). In other words, there is exactly one tower of height \(1\), and all other towers have a height of \(0\).

In this state, the only “visible tower” is the single tower where the block was placed (\(1\) tower). No matter how cleverly we place the block, it is impossible to make \(2\) or more towers visible immediately after the first step.

2. The Case where \(K \ge 2\)

Immediately after the first step, no matter what we do, only \(1\) tower is visible. Therefore, if \(K \ge 2\), the condition of having “at least \(K\) visible towers” will inevitably be violated at the very first step. Thus, the answer for \(K \ge 2\) is always \(0\).

3. The Case where \(K = 1\)

The condition becomes “at least \(1\) tower is always visible.” As long as at least \(1\) block has been placed, there is at least one tower with a height of \(1\) or more. If we look at the towers from left to right, the first tower we encounter with a height of \(1\) or more will always satisfy the condition of being a “visible tower” because there are no towers with a height of \(1\) or more to its left.

In other words, as long as there is at least \(1\) block, there is always at least \(1\) visible tower. Therefore, when \(K = 1\), the condition is always satisfied no matter what order we stack the blocks in.

4. Counting the Sequences

When \(K = 1\), the problem simply reduces to finding “the total number of ways to stack \(H_i\) blocks on the \(i\)-th tower.” Let the total number of blocks be \(S = \sum_{i=1}^{N} H_i\). Since this is equivalent to choosing \(H_i\) steps out of \(S\) steps to place blocks on the \(i\)-th tower, we can calculate this as a permutation with repetition (multinomial coefficient) as follows:

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

Algorithm

1. If \(K \ge 2\), immediately output 0 and terminate.
2. If \(K = 1\):
   • Calculate the sum of \(H_i\), which is \(S = \sum H_i\).
   • Precompute the factorials \(x! \pmod{10^9+7}\) for \(0\) to \(S\).
   • Calculate the multinomial coefficient by multiplying the numerator \(S!\) by the modular inverse of each denominator \(H_i!\). The modular inverse can be calculated using Fermat’s Little Theorem (\(a^{-1} \equiv a^{MOD-2} \pmod{MOD}\)) and binary exponentiation.

Complexity

• Time Complexity: \(O(S + N \log(\text{MOD}))\)
  • Here, \(S = \sum H_i \le 10^6\). It takes \(O(S)\) to generate the factorial table and \(O(\log(\text{MOD}))\) to calculate the modular inverse of each \(H_i!\). This is fast enough to run well within the time limit.
• Space Complexity: \(O(S + N)\)
  • It uses \(O(S)\) memory for the array storing factorials and \(O(N)\) memory to store the input.

Implementation Points

• Modular Inverse Calculation: Since \(10^9+7\) is a prime number, we can find the modular inverse using fast exponentiation (binary exponentiation) based on Fermat’s Little Theorem.

• Fast I/O: Since \(N\) and \(S\) can be up to \(10^6\), it is safe to speed up input/output in C++ using cin.tie(NULL) and ios_base::sync_with_stdio(false).

  Source Code

#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;
}

---

This editorial was generated by gemini-3.5-flash-high.