trang chủ / đề bài / icpc26_mb_i

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 a[1..N] 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, swap(a[i],a[j]) là thao tác đổi chỗ hai giá trị đang nằm ở chỉ số i và j. 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 p của {1,2,…,N} đượ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ỉ A/B. Hãy tính A×B−1mod998244353, trong đó B−1 là nghịch đảo modulo của B theo modulo 998244353.

Dữ liệu vào

  • Dòng đầu tiên chứa một số nguyên T (1≤T≤105): số bộ dữ liệu.
  • Mỗi dòng trong T dòng tiếp theo chứa một số nguyên N (1≤N≤105).

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 998244353.

Ràng buộc

  • 1≤T≤105.
  • 1≤N≤105.

Ví dụ

Input Output Giải thích
2
3
46192
166374062
504875816
Với N=3 có 6 hoán vị đồng khả năng của [1,2,3]: [1,2,3] cần 4 phép đổi chỗ, [1,3,2] cần 3, [2,1,3] cần 3, [2,3,1] cần 4, [3,1,2] cần 2, [3,2,1] cần 3. Số phép đổi chỗ kỳ vọng là (4+3+3+4+2+3)/6=19/6≡19×6−1≡166374062(mod998244353).
3
1
2
4
0
499122178
166374064
Ví dụ bổ sung. Với N=1 không có phép đổi chỗ nào. Với N=2: [1,2] cần 2 phép đổi chỗ (thành [2,1] rồi lại [1,2]), [2,1] cần 1, kỳ vọng 3/2. Với N=4 kỳ vọng là 31/6.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0