概要

\(A \times B \times C\) 種類のお弁当の中から \(N\) 個を選び、\(N\) 人の社員にそれぞれ異なるものを割り当てる方法の数を求める問題です。

考察

まず、お弁当の総数を考えます。メインおかずが \(A\) 種類、サイドおかずが \(B\) 種類、デザートが \(C\) 種類あるため、お弁当の組み合わせは全部で \(M = A \times B \times C\) 種類存在します。

この \(M\) 種類のお弁当の中から \(N\) 人に異なるものを割り当てる方法の数を求めます。 - \(1\) 人目の社員のお弁当の選び方は、\(M\) 通りあります。 - \(2\) 人目の社員は、\(1\) 人目が選んだお弁当以外の \(M - 1\) 通りから選びます。 - \(3\) 人目の社員は、\(M - 2\) 通りから選びます。 - これを繰り返し、\(N\) 人目の社員は \(M - N + 1\) 通りから選びます。

したがって、求める答えは以下の式で表される順列の数 \({}_M P_N\) となります。 \(M \times (M - 1) \times (M - 2) \times \dots \times (M - N + 1)\)

ここで注意すべき点として、\(M\) は最大で \(10^6 \times 10^6 \times 10^6 = 10^{18}\) という非常に大きな値になります。そのため、階乗を使って \(\frac{M!}{(M-N)!}\) を計算しようとすると、\(M\) 回のループが必要になり、確実にTLE（実行時間超過）となってしまいます。

しかし、今回お弁当を割り当てる人数 \(N\) は最大でも \(10^6\) です。上記の式を見ると掛け算を行う回数はちょうど \(N\) 回なので、\(N\) 回のループであれば制限時間内に十分計算できることに気づくのが重要なポイントです。

アルゴリズム

1. お弁当の総数 \(M = A \times B \times C\) を計算し、あらかじめ \(10^9 + 7\) で割った余りを求めておきます。
2. 答えを格納する変数 ans を \(1\) で初期化します。
3. \(i = 0, 1, 2, \dots, N-1\) について、以下の計算を繰り返します。
   • ans に \((M - i)\) を掛け、\(10^9 + 7\) で割った余りを ans に代入します。
4. 最終的な ans の値を出力します。

計算量

• 時間計算量: \(O(N)\) \(N\) 回のループを回して掛け算を行うため、計算量は \(N\) に比例します。最大で \(10^6\) 回の演算となり、制限時間（通常2秒）に十分間に合います。
• 空間計算量: \(O(1)\) 配列などは使用せず、いくつかの変数のみを保持するため、メモリ使用量は定数となります。

実装のポイント

• 大きな数の掛け算: \(A, B, C\) を掛け合わせると最大 \(10^{18}\) になるため、C++やJavaなどの言語を使用する場合は、オーバーフローを防ぐために64ビット整数型（long long など）を使用する必要があります（Pythonでは自動的に多倍長整数として扱われるため、型の心配は不要です）。

• 負の剰余（モジュロ）演算: コード内で M = (A * B * C) % MOD としているため、\(i\) が大きくなると M - i が負の値になることがあります。Pythonの % 演算子は負の数に対しても数学的に正しい正の余りを返す（例：-2 % 7 = 5）ため、そのまま計算して問題ありません。もしC++などで実装する場合は、(M - i % MOD + MOD) % MOD のように、値が負にならないよう調整する工夫が必要です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    A = int(input_data[1])
    B = int(input_data[2])
    C = int(input_data[3])
    
    MOD = 10**9 + 7
    
    M = (A * B * C) % MOD
    ans = 1
    for i in range(N):
        ans = (ans * (M - i)) % MOD
        
    print(ans)

if __name__ == '__main__':
    main()

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