หาผลคูณของ N แฟกทอเรียลแรก (Product of First N Factorials) ใน C++

งานคือหาผลคูณของแฟกทอเรียล N ตัวแรก: 1! × 2! × 3! × ... × N! แล้ว modulo 1,000,000,007 (1e9+7)

Constraint: 1 ≤ N ≤ 10⁶

ตัวอย่าง

N = 3

1! = 1
2! = 2
3! = 6
ผลคูณ = 1 × 2 × 6 = 12

Output: 12

N = 9

Output: 27

1!×2!×...×9! mod 1e9+7 = 27

แนวทางแก้ปัญหา

คำนวณแบบทบต้น (Iterative) เพื่อไม่ต้องคำนวณแฟกทอเรียลซ้ำ:

1. fact = 1 (เก็บ i!)
2. prod = 1 (เก็บผลคูณสะสม)
3. วน i = 1 ถึง N:
   • fact = (fact × i) % MOD → ได้ i!
   • prod = (prod × fact) % MOD → คูณสะสม

ตัวอย่างโค้ด (ปรับปรุงจากต้นฉบับ)

#include <iostream>
using namespace std;

const long long MOD = 1000000007LL;

long long productOfFactorials(int N) {
    long long fact = 1;
    long long prod = 1;
    for (int i = 1; i <= N; i++) {
        fact = (fact * i) % MOD;
        prod = (prod * fact) % MOD;
        if (prod == 0) return 0;  // หาร MOD ลงตัว
    }
    return prod;
}

int main() {
    int N = 3;
    cout << "Product of first " << N << " factorials: " 
         << productOfFactorials(N) << endl;
    
    N = 9;
    cout << "Product of first " << N << " factorials: " 
         << productOfFactorials(N) << endl;
    
    N = 1000000;
    cout << "Product of first " << N << " factorials: " 
         << productOfFactorials(N) << endl;
    return 0;
}

ผลลัพธ์

Product of first 3 factorials: 12
Product of first 9 factorials: 27
Product of first 1000000 factorials: 0

N=10⁶ ให้ 0 เพราะแฟกทอเรียลจะมีตัวคูณ 1e9+7 เข้าไป (1e9+7 เป็นเฉพาะ) ทำให้ mod = 0

ข้อสังเกตจากโค้ดต้นฉบับ

• ใช้ mulmod แบบ Russian Peasant (double-and-add) ซึ่งไม่จำเป็น เพราะ long long (64-bit) รองรับ (1e9+7)² ≈ 1e18 ไม่ล้น
• การคูณตรง (a * b) % MOD ทำงานได้ถูกต้องและเร็วกว่า
• โค้ดต้นฉบับมี typo: 1e9 + 7 เป็น double ควรเป็น 1000000007LL

ความซับซ้อน

• เวลา: O(N) – ลูปเดี่ยว N รอบ
• พื้นที่: O(1)

การประยุกต์ใช้

โจทย์นี้เกี่ยวข้องกับ Superfactorial (Sloane's A000178) และมีการประยุกต์ใน組合数学 (Combinatorics) และทฤษฎีจำนวน