概要

\(A \times B \times C\) 種類のお弁当の中から \(N\) 個の異なるお弁当を選び、\(N\) 人の社員に割り当てる方法の数を \(10^9 + 7\) で割った余りで求める問題です。これは順列（Permutation）の計算に帰着されます。

考察

問題の言い換え

お弁当は（メインおかず、サイドおかず、デザート）の3つ組で決まり、全部で \(M = A \times B \times C\) 種類あります。\(N\) 人の社員はそれぞれ区別され、全員に異なるお弁当を1つずつ割り当てます。

これは「\(M\) 個の異なるものから \(N\) 個を選んで、\(N\) 人に順番に配る」ことと同じです。つまり、求める答えは順列 \(P(M, N)\) です。

\[P(M, N) = M \times (M-1) \times (M-2) \times \cdots \times (M-N+1)\]

具体例

例えば \(A = 2, B = 2, C = 2\) のとき \(M = 8\) 種類のお弁当があります。\(N = 3\) 人なら：

\[P(8, 3) = 8 \times 7 \times 6 = 336\]

• 1人目に8通り、2人目に残り7通り、3人目に残り6通りです。

\(M\) が巨大になる問題

\(A, B, C\) はそれぞれ最大 \(10^6\) なので、\(M = A \times B \times C\) は最大で \(10^{18}\) にもなります。しかし、計算は \(\mod (10^9 + 7)\) で行うため、\(M\) そのものを正確に保持する必要はありません。

\(M \mod p\)（\(p = 10^9 + 7\)）を先に計算しておけば、各項 \((M - i) \mod p\) は次のように求まります：

\[(A \times B \times C - i) \mod p = ((A \times B \times C \mod p) - (i \mod p)) \mod p\]

これは剰余演算の性質から正しく成り立ちます。

アルゴリズム

1. \(M = A \times B \times C \mod (10^9 + 7)\) を計算する
2. \(\text{result} = 1\) と初期化する
3. \(i = 0, 1, 2, \ldots, N-1\) に対して、\(\text{result}\) に \((M - i) \mod (10^9 + 7)\) を掛けていく
4. 最終的な \(\text{result}\) を出力する

これは \(P(M, N) \mod (10^9 + 7)\) を直接計算していることになります。

計算量

• 時間計算量: \(O(N)\) — ループを \(N\) 回まわして掛け算するだけです（\(N \leq 10^6\) なので十分高速）
• 空間計算量: \(O(1)\) — 定数個の変数のみ使用します

実装のポイント

• \(M\) のオーバーフロー防止: \(A \times B \times C\) は最大 \(10^{18}\) になるため、先に \(\mod\) を取って計算します。Python は多倍長整数なのでオーバーフローの心配はありませんが、剰余を先に取ることで効率的に計算できます。

• 負の剰余に注意: \((M - i) \mod p\) が負になる可能性があります（\(M\) は \(\mod\) を取った後の値なので、\(i\) が大きいと \(M - i < 0\) になりえます）。Python では % 演算子が常に非負の値を返すため、特別な処理は不要ですが、他の言語（C++ など）では ((M - i) % MOD + MOD) % MOD とする必要があります。

• \(N \leq A \times B \times C\) の保証: 問題文で保証されているため、掛ける値が途中で \(0 \mod p\) にならない限り、答えが \(0\) になることは基本的にありません（ただし \(\mod p\) の世界では \(0\) になる場合もあり、それはそのまま正しい答えです）。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    A = int(input_data[1])
    B = int(input_data[2])
    C = int(input_data[3])
    
    MOD = 10**9 + 7
    
    # Total number of bento types: M = A * B * C
    # We need to assign N distinct bentos to N distinct people
    # This is P(M, N) = M * (M-1) * (M-2) * ... * (M-N+1)
    # where M = A * B * C
    
    # But M can be up to 10^18, so we can't compute M directly and then do modular arithmetic
    # Wait, actually we can. M mod p is fine, and then M-1 mod p, etc.
    # But M can be up to 10^18. We just need M mod MOD, (M-1) mod MOD, ..., (M-N+1) mod MOD
    
    # M = A * B * C mod MOD
    M = (A % MOD) * (B % MOD) % MOD * (C % MOD) % MOD
    
    # P(M, N) = M * (M-1) * ... * (M-N+1) mod MOD
    # We need to compute this product where each term is (M - i) mod MOD for i = 0, 1, ..., N-1
    # But M here is already reduced mod MOD. Since A*B*C can be up to 10^18,
    # we need to be careful: (M - i) mod MOD where M is the actual value A*B*C
    # Since we work mod MOD, (A*B*C - i) mod MOD = (M_mod - i % MOD) % MOD where M_mod = A*B*C mod MOD
    # This is correct because (A*B*C - i) mod MOD = ((A*B*C mod MOD) - (i mod MOD)) mod MOD
    
    result = 1
    for i in range(N):
        result = result * ((M - i) % MOD) % MOD
    
    print(result % MOD)

solve()

---

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