Find the Derangement of An Array – หาจำนวนการเรียงลำดับเดอะรองเมนต์ใน C++

ปัญหา: Find the Derangement of An Array

อาร์เรย์ [1, 2, ..., n] หาจำนวน Derangements (การเรียงใหม่ที่ ไม่มีตัวเลขใดอยู่ตำแหน่งเดิม)
คำตอบ modulo 10^9 + 7

ตัวอย่าง

n = 3: [1,2,3] → Derangements: [2,3,1], [3,1,2] → Output: 2

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

Recurrence (Derangement Formula)

D(n) = (n-1) × [D(n-1) + D(n-2)]

พิสูจน์: วางตัว n ไปที่ตำแหน่ง k (มี n-1 ทางเลือก)
- กรณี 1: ตัว k ไปที่ตำแหน่ง n → เหลือ derange n-2 ตัว → D(n-2)
- กรณี 2: ตัว k ไปที่อื่น (ไม่ใช่ n) → เหลือ derange n-1 ตัว (k ห้ามอยู่ตำแหน่ง k, n ห้ามอยู่ n) → D(n-1)

Base Cases

• D(1) = 0
• D(2) = 1 ([2,1])

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

class Solution {
public:
    int findDerangement(int n) {
        if (n == 1) return 0;
        if (n == 2) return 1;

        vector<long long> dp(n + 1);
        dp[1] = 0;
        dp[2] = 1;

        for (int i = 3; i <= n; i++) {
            dp[i] = (i - 1) * (dp[i-1] + dp[i-2]) % MOD;
        }
        return dp[n];
    }
};

// Space optimized O(1)
int findDerangementOptimized(int n) {
    if (n == 1) return 0;
    if (n == 2) return 1;
    long long a = 0, b = 1; // D(1), D(2)
    for (int i = 3; i <= n; i++) {
        long long c = (i - 1) * (a + b) % MOD;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    Solution ob;
    for (int n = 1; n <= 10; n++)
        cout << "D(" << n << ") = " << ob.findDerangement(n) << '\n';
    // D(1)=0, D(2)=1, D(3)=2, D(4)=9, D(5)=44, D(6)=265...
    return 0;
}

สูตรปิด (Closed Form)

D(n) = n! × Σ_{k=0}^{n} (-1)^k / k! ≈ round(n! / e)

ความซับซ้อน

• เวลา: O(n)
• พื้นที่: O(n) หรือ O(1) (optimized)

ข้อสังเกต

• LeetCode 634
• Derangement เรียกว่า "Subfactorial" เขียนว่า !n
• Modulo 10^9+7 ต้องทำทุกขั้นตอนป้องกัน overflow
• โค้ดต้นฉบับมี helper add(), mul() – ไม่จำเป็นถ้าใช้ long long และ modulo ตรงๆ