概要

\(N\) 個の部屋を順番に通り抜ける際、各部屋にある複数のドアから1つを選ぶという試行を \(N\) 回繰り返します。このとき、入口から出口までに通り得る経路の総数を求める問題です。

考察

この問題は、組み合わせ数学における「積の法則」を適用することで解くことができます。

例えば、部屋が 2 つあり、部屋 1 に 2 枚のドア（a, b）、部屋 2 に 3 枚のドア（x, y, z）がある場合を考えてみましょう。 - 部屋 1 でドア a を選んだとき、部屋 2 での選び方は x, y, z の 3 通りあります。 - 部屋 1 でドア b を選んだとき、部屋 2 での選び方は x, y, z の 3 通りあります。 したがって、合計の経路は \(2 \times 3 = 6\) 通りとなります。

これを \(N\) 個の部屋に拡張すると、全体の経路の総数は各部屋のドアの数の総乗、すなわち $\(A_1 \times A_2 \times \cdots \times A_N\)$ で求められます。

制約を確認すると、答えの最大値は \(10^{18}\) とされています。これは多くのプログラミング言語の 64 ビット整数型（C++ の long long など）に収まる範囲内であり、Python の場合は標準で多倍長整数（桁数に制限のない整数）をサポートしているため、オーバーフローを気にせず計算することが可能です。

アルゴリズム

1. 答えを格納する変数 ans を \(1\) で初期化します。
2. 部屋 \(1\) から 部屋 \(N\) まで順番に、ドアの数 \(A_i\) を ans に掛け合わせます。
3. 最終的な ans の値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 部屋の数 \(N\) に対して、掛け算を \(N\) 回行うため、ループの回数は \(N\) に比例します。
• 空間計算量: \(O(N)\)
  • 入力値をすべてリストとして読み込む場合、部屋の数 \(N\) に比例したメモリを使用します。

実装のポイント

• 大きな数の扱い: 今回の制約では積が \(10^{18}\) 以下に収まることが保証されていますが、Python を使用することで、より大きな数値の結果になる場合でも安全に計算できます。

• 入力の受け取り: \(N\) が最大 \(10^5\) と比較的大きいため、sys.stdin.read().split() を用いて一括で入力を取得することで、効率的に処理を行っています。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白文字で分割します
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
    
    # 部屋の数 N を取得
    n = int(input_data[0])
    
    # 経路の総数は各部屋のドアの数の積 A_1 * A_2 * ... * A_N です
    # Pythonは標準で多倍長整数をサポートしているため、オーバーフローの心配はありません
    ans = 1
    for i in range(1, n + 1):
        ans *= int(input_data[i])
        
    # 結果を出力
    print(ans)

if __name__ == '__main__':
    solve()

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