Dị thường sắp xếp lõi lượng tử
Đề bài
Mô tả
Tại bộ phận bảo trì của Khu vực 2026, các nhà nghiên cứu phát hiện một bộ xử lý dữ liệu tự động cổ xưa. Để ổn định các tinh thể năng lượng, bộ xử lý sắp xếp một mảng bằng một thủ tục khác thường như sau:
for i = 1, 2, ..., N:
for j = 1, 2, ..., N:
if a[i] < a[j]:
swap a[i] and a[j]
Ở đây, là thao tác đổi chỗ hai giá trị đang nằm ở chỉ số và . Dù cấu trúc kỳ lạ, thủ tục này được đảm bảo về mặt toán học là luôn sắp xếp mọi mảng theo thứ tự không giảm.
Độ kém hiệu quả vận hành của cỗ máy trên một hoán vị được đo bằng tổng số phép đổi chỗ được thực hiện trong quá trình sắp xếp. Giả sử hoán vị ban đầu của được chọn ngẫu nhiên đều, hãy tính giá trị kỳ vọng của độ kém hiệu quả của cỗ máy.
Có thể chứng minh rằng giá trị kỳ vọng là một số hữu tỉ . Hãy tính , trong đó là nghịch đảo modulo của theo modulo .
Dữ liệu vào
- Dòng đầu tiên chứa một số nguyên (): số bộ dữ liệu.
- Mỗi dòng trong dòng tiếp theo chứa một số nguyên ().
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một số nguyên: độ kém hiệu quả kỳ vọng theo modulo .
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 46192 |
166374062 504875816 |
Với có hoán vị đồng khả năng của : cần phép đổi chỗ, cần , cần , cần , cần , cần . Số phép đổi chỗ kỳ vọng là . |
| 3 1 2 4 |
0 499122178 166374064 |
Ví dụ bổ sung. Với không có phép đổi chỗ nào. Với : cần phép đổi chỗ (thành rồi lại ), cần , kỳ vọng . Với kỳ vọng là . |
Bình luận