概要

各ステップで「見える塔」が \(K\) 本以上必要です。実は \(K \geq 2\) の場合は最初の1手目で必ず条件を満たせないため不可能で、\(K=1\) の場合はすべての積み方が有効になります。

考察

まず、最初の1ステップ目を考えます。

初期状態ではすべての塔の高さは \(0\) です。
1ステップ目では、どれか1つの塔にブロックを1個だけ積みます。

このとき、高さが \(1\) 以上の塔は1本だけです。
したがって、見える塔の本数も必ず \(1\) 本です。

つまり、\(K \geq 2\) の場合、1ステップ目の直後に条件

\[ \text{見える塔の本数} \geq K \]

を満たすことができません。

よって、\(K > 1\) なら答えは必ず \(0\) です。

---

次に \(K=1\) の場合を考えます。

この場合、各ステップの直後に「見える塔が少なくとも1本あればよい」です。

少なくとも1個以上ブロックが積まれている状態では、必ず見える塔が1本以上存在します。

なぜなら、現在の高さの最大値を持つ塔のうち、最も左にある塔を考えます。
その塔の高さを \(m\) とすると、\(m \geq 1\) です。

また、それより左にある塔はすべて高さが \(m\) 未満です。
したがって、その塔は

\[ h_i > \max(h_1, h_2, \ldots, h_{i-1}) \]

を満たすので、必ず見えます。

つまり、\(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!} \]

です。

これを \(10^9+7\) で割った余りとして求めます。

アルゴリズム

1. 入力を受け取る。
2. \(K > 1\) なら、答えは \(0\) なので即座に出力する。
3. \(K=1\) の場合、\(S=\sum H_i\) を計算する。
4. \(0!\) から \(S!\) までの階乗を前計算する。
5. 逆元を使って、階乗の逆数も前計算する。
6. 答えを次の式で計算する。

\[ \text{ans} = S! \times \frac{1}{H_1!} \times \frac{1}{H_2!} \times \cdots \times \frac{1}{H_N!} \]

mod \(10^9+7\) で計算します。

法 \(10^9+7\) は素数なので、フェルマーの小定理より

\[ a^{-1} \equiv a^{MOD-2} \pmod{MOD} \]

で逆元を求めることができます。

計算量

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

ただし、

\[ S = \sum_{i=1}^{N} H_i \]

です。制約より \(S \leq 10^6\) なので十分高速です。

実装のポイント

\(K>1\) の場合は、最初の1手目の時点で条件を満たせないため、階乗などを計算せずすぐに 0 を出力します。

\(K=1\) の場合は、多項係数を求めます。

ans = fact[S]
for h in H:
    ans = ans * invfact[h] % MOD

これは

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

を計算している部分です。

ソースコード

import sys

MOD = 10**9 + 7

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    H = data[2:]

    if K > 1:
        print(0)
        return

    S = sum(H)

    fact = [1] * (S + 1)
    for i in range(1, S + 1):
        fact[i] = fact[i - 1] * i % MOD

    invfact = [1] * (S + 1)
    invfact[S] = pow(fact[S], MOD - 2, MOD)
    for i in range(S, 0, -1):
        invfact[i - 1] = invfact[i] * i % MOD

    ans = fact[S]
    for h in H:
        ans = ans * invfact[h] % MOD

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。