概要

ブロックを 1 個ずつ積んでいく作業手順のうち、「各ステップ直後に左から見える塔が \(K\) 本以上」という条件を常に満たすものの総数を求める問題です。実は答えは \(K\) の値によって大きく変わり、\(K \geq 2\) なら \(0\)、\(K = 1\) なら多項係数（マルチノミアル係数）になります。

考察

「見える塔」の本数の最小値に注目する

まず、最初の \(1\) ステップを行った直後を考えてみましょう。このとき積まれているブロックはちょうど \(1\) 個なので、高さ \(\geq 1\) の塔はただ \(1\) 本だけです。

その唯一の高さ \(\geq 1\) の塔（仮に塔 \(j\) とする）について、左側の塔はすべて高さ \(0\) なので \(h_j \geq 1 > 0 = \max\) となり、必ず「見える」状態になります。つまり最初のステップ直後に見える塔は ちょうど \(1\) 本 です。

したがって、

• \(K \geq 2\) のとき：最初の \(1\) ステップの直後で見える塔が \(1\) 本しかないため、条件を満たせません。よって答えは \(0\)。

\(K = 1\) のときは常に条件を満たす

逆に \(K = 1\) のときは、どのステップの直後でも必ず条件を満たすことが示せます。

任意のステップ直後を考えると、これまでに少なくとも \(1\) 個はブロックを積んでいるので、高さ \(\geq 1\) の塔が必ず存在します。その中で 一番左にある塔 を塔 \(i\) とすると、塔 \(i\) より左の塔はすべて高さ \(0\) です。よって \(h_i \geq 1 > 0 = \max(h_1,\ldots,h_{i-1})\) が成り立ち、塔 \(i\) は必ず見えます。

つまり、いつでも見える塔は 最低 \(1\) 本 存在するので、\(K = 1\) の条件は積む順番に関係なく常に満たされます。

手順の総数を数える

\(K = 1\) では順番の制約が一切ないので、「どんな順番で積んでもよい」状況になります。

塔 \(i\) には \(H_i\) 個のブロックを積みますが、同じ塔に積む操作どうしは区別できません（「塔 \(i\) にブロックを載せる」という同じ操作）。\(S = \sum H_i\) 個の操作を一列に並べ、そのうち塔ごとの操作を区別しない並べ方の総数は、多項係数

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

で与えられます。これが答えです。

具体例

例えば \(N = 2\), \(H = (2, 1)\), \(K = 1\) の場合、\(S = 3\) なので

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

通り。実際、塔 \(1\) に積む操作を「A」、塔 \(2\) に積む操作を「B」と書くと、AAB, ABA, BAA の \(3\) 通りで一致します。

アルゴリズム

1. \(K \geq 2\) なら \(0\) を出力して終了。
2. \(K = 1\) なら、\(S = \sum H_i\) として多項係数 \(\dfrac{S!}{\prod_i H_i!}\) を \(10^9 + 7\) で割った余りで求める。
   • 階乗 \(0!, 1!, \ldots, S!\) を前計算し、フェルマーの小定理で \(S!\) の逆元を求め、そこから各逆階乗を順に計算する。
   • 答えは \(S! \times \prod_i (H_i!)^{-1} \bmod (10^9+7)\)。

計算量

• 時間計算量: \(O(S + N)\)（\(S = \sum H_i \leq 10^6\)）
• 空間計算量: \(O(S)\)

実装のポイント

• 多項係数を求めるには、\(S!\) の逆元を一度だけ \(\mathrm{pow}(S!, p-2, p)\) で計算し、漸化式 \((\text{inv\_fact}[i-1] = \text{inv\_fact}[i] \times i)\) で逆階乗を一括計算すると効率的です。これにより、モジュラ逆元の計算が \(1\) 回で済みます。

• \(H_i \geq 1\) なので \(S \geq 1\) が保証され、階乗テーブルのサイズ確保で問題は起きません。

• \(K \geq 2\) の判定を最初に行うことで、不要な計算を避けられます。

  ソースコード

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()

---

この解説は claude4.8opus-high によって生成されました。