Tìm hoán vị hoàn toàn của mảng trong C++

Giới thiệu

Cho mảng [1, 2, ..., n]. Hoán vị hoàn toàn (derangement) là hoán vị không có phần tử nào ở vị trí gốc. Tìm số lượng derangement modulo 10^9+7.

Công thức truy hồi

Gọi D(n) là số derangement của n phần tử.

• D(1) = 0
• D(2) = 1 ([2,1])
• D(n) = (n-1) * (D(n-1) + D(n-2)) cho n ≥ 3.

Chứng minh: Xét phần tử 1. Nó đi đến vị trí k (k ≠ 1, có n-1 cách chọn).

• Nếu phần tử k đi đến vị trí 1 → còn n-2 phần tử cần derange: D(n-2).
• Nếu phần tử k KHÔNG đi đến vị trí 1 → bài toán quy về derange n-1 phần tử (với điều kiện k không về 1): D(n-1).

Cài đặt 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 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];
    }
};

int main() {
    Solution ob;
    cout << ob.findDerangement(3); // Output: 2 ([2,3,1] và [3,1,2])
    return 0;
}

Phân tích

• Thời gian: O(n).
• Không gian: O(n) (có thể tối ưu O(1) chỉ giữ 2 giá trị trước).

LeetCode 634 "Find the Derangement of An Array".