Đề bài
Năm người bạn bỏ mũ vào một đống, rồi mỗi người lấy lại ngẫu nhiên một chiếc. Có bao nhiêu cách để không ai lấy đúng mũ của mình? Một cách sắp xếp n phần tử mà không phần tử nào ở lại vị trí cũ được gọi là hoán vị không có điểm cố định (derangement). Số cách như vậy lần lượt là 1, 0, 1, 2, 9, 44 và tuân theo công thức D(n) = (n − 1) × (D(n − 1) + D(n − 2)).
Hãy viết derangements(n).
Đầu vào
n: Số phần tử.
Đầu ra
Trả về số hoán vị không có điểm cố định của n phần tử. D(0) bằng 1 (cách sắp xếp rỗng không có phần tử nào có thể đứng yên) và D(1) bằng 0.
Ràng buộc
0 ≤ n ≤ 20
Ví dụ
Đầu vào:
n = 3
Kết quả mong đợi:
expected = 2
Đầu vào:
long long n = 3;
Kết quả mong đợi:
long long expected = 2;
Đầu vào:
long n = 3;
Kết quả mong đợi:
long expected = 2;
Giải thích
Với các phần tử A, B, C, chỉ có BCA và CAB là làm mọi phần tử đổi chỗ, nên đáp án là 2.
Đầu vào:
n = 4
Kết quả mong đợi:
expected = 9
Đầu vào:
long long n = 4;
Kết quả mong đợi:
long long expected = 9;
Đầu vào:
long n = 4;
Kết quả mong đợi:
long expected = 9;
Giải thích
D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Bắt đầu từ D(0) = 1 và D(1) = 0.
Gợi ý 2
Mỗi giá trị tiếp theo dùng hai giá trị trước đó và n hiện tại.
Gợi ý 3
Tại mỗi thời điểm chỉ cần hai giá trị gần nhất.
Độ phức tạp mong đợi
thời gian O(n), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.