Overview

This problem asks us to find the number of ways to stack blocks one by one such that the condition “at least \(K\) towers are visible from the left immediately after each step” is always satisfied. In fact, the answer varies greatly depending on the value of \(K\): it is \(0\) if \(K \geq 2\), and a multinomial coefficient if \(K = 1\).

Analysis

Focusing on the minimum number of “visible towers”

First, let us consider the state immediately after the first step. Since exactly \(1\) block has been stacked at this point, there is only one tower with a height of \(\geq 1\).

For this unique tower of height \(\geq 1\) (let’s call it tower \(j\)), all towers to its left have a height of \(0\). Thus, \(h_j \geq 1 > 0 = \max\) holds, making it always “visible”. In other words, immediately after the first step, the number of visible towers is exactly \(1\).

Therefore,

• When \(K \geq 2\): Immediately after the first step, there is only \(1\) visible tower, so the condition cannot be satisfied. Thus, the answer is \(0\).

When \(K = 1\), the condition is always satisfied

Conversely, when \(K = 1\), we can show that the condition is always satisfied after any step.

Consider the state immediately after any step. Since at least \(1\) block has been stacked so far, there must exist at least one tower with height \(\geq 1\). Let the leftmost tower among them be tower \(i\). All towers to the left of tower \(i\) have a height of \(0\). Thus, \(h_i \geq 1 > 0 = \max(h_1,\ldots,h_{i-1})\) holds, and tower \(i\) is guaranteed to be visible.

In other words, there is always at least \(1\) visible tower at any time. Thus, the condition for \(K = 1\) is always satisfied, regardless of the order in which the blocks are stacked.

Counting the number of valid sequences

Since there are no constraints on the order when \(K = 1\), we can stack the blocks in any order.

We stack \(H_i\) blocks on tower \(i\), but operations of stacking on the same tower are indistinguishable (they are the same operation: “place a block on tower \(i\)”). The total number of ways to arrange \(S = \sum H_i\) operations in a line, without distinguishing operations on the same tower, is given by the multinomial coefficient:

\[ \frac{S!}{H_1! \, H_2! \, \cdots \, H_N!} \]

This is the answer.

Example

For example, if \(N = 2\), \(H = (2, 1)\), and \(K = 1\), then \(S = 3\), so we have:

\[ \frac{3!}{2! \cdot 1!} = \frac{6}{2} = 3 \]

ways. Indeed, if we represent stacking on tower \(1\) as “A” and stacking on tower \(2\) as “B”, the \(3\) possible sequences are AAB, ABA, and BAA, which matches the result.

Algorithm

1. If \(K \geq 2\), output \(0\) and terminate.
2. If \(K = 1\), let \(S = \sum H_i\) and compute the multinomial coefficient \(\dfrac{S!}{\prod_i H_i!}\) modulo \(10^9 + 7\).
   • Precompute the factorials \(0!, 1!, \ldots, S!\), find the modular inverse of \(S!\) using Fermat’s Little Theorem, and then compute each inverse factorial in reverse order.
   • The answer is \(S! \times \prod_i (H_i!)^{-1} \bmod (10^9+7)\).

Complexity

• Time Complexity: \(O(S + N)\) (where \(S = \sum H_i \leq 10^6\))
• Space Complexity: \(O(S)\)

Implementation Details

• To find the multinomial coefficient efficiently, we can compute the modular inverse of \(S!\) only once using \(\mathrm{pow}(S!, p-2, p)\), and then compute all inverse factorials in bulk using the recurrence relation \((\text{inv\_fact}[i-1] = \text{inv\_fact}[i] \times i)\). This reduces the number of modular inverse operations to just \(1\).

• Since \(H_i \geq 1\), \(S \geq 1\) is guaranteed, so there are no issues with allocating the size of the factorial tables.

• By checking the condition \(K \geq 2\) first, we can avoid unnecessary computations.

  Source Code

import sys

def main():
    MOD = 10**9 + 7
    data = sys.stdin.buffer.read().split()
    N = int(data[0]); K = int(data[1])
    H = list(map(int, data[2:2+N]))

    if K >= 2:
        print(0)
        return

    S = sum(H)
    # 階乗・逆階乗の前計算
    fact = [1] * (S + 1)
    for i in range(1, S + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact = [1] * (S + 1)
    inv_fact[S] = pow(fact[S], MOD - 2, MOD)
    for i in range(S, 0, -1):
        inv_fact[i-1] = inv_fact[i] * i % MOD

    ans = fact[S]
    for h in H:
        ans = ans * inv_fact[h] % MOD
    print(ans)

main()

---

This editorial was generated by claude4.8opus-high.