trang chủ / đề bài / icpc23_nat_j

Đồ thị xáo trộn

Đề bài

Mô tả

Hãy cùng xem lại một bài toán rất cơ bản của lý thuyết đồ thị: cho một đồ thị vô hướng liên thông gồm n đỉnh (đánh số từ 1 đến n), thứ tự duyệt theo chiều sâu (DFS) của đồ thị là gì? Thứ tự DFS có thể được sinh ra bởi đoạn mã giả sau:

dfs_order = []      # danh sách rỗng

def DFS(u):
    visited[u] = True
    dfs_order.append(u)
    for vertex v that is directly connected to u:
        # lưu ý: thứ tự duyệt các đỉnh v là hoàn toàn ngẫu nhiên
        if visited[v] == False:
            DFS(v)

DFS(random(1,n))

Ví dụ, đồ thị 4 đỉnh với các cạnh 1−2, 1−3, 1−4, 2−4 có 12 thứ tự DFS hợp lệ:

  1. 1, 2, 4, 3
  2. 1, 3, 2, 4
  3. 1, 3, 4, 2
  4. 1, 4, 2, 3
  5. 2, 1, 3, 4
  6. 2, 1, 4, 3
  7. 2, 4, 1, 3
  8. 3, 1, 2, 4
  9. 3, 1, 4, 2
  10. 4, 1, 2, 3
  11. 4, 1, 3, 2
  12. 4, 2, 1, 3

Cho một hoán vị của 1 đến n, hãy đếm xem có bao nhiêu đồ thị vô hướng nhận hoán vị này là một thứ tự DFS hợp lệ. Lưu ý rằng hai đồ thị G1 và G2 được coi là khác nhau khi và chỉ khi tồn tại hai đỉnh u và v (u≠v) sao cho G1 có cạnh nối u và v còn G2 thì không, hoặc ngược lại.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n (1≤n≤16), số đỉnh.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an biểu diễn một thứ tự DFS. Dữ liệu bảo đảm (a1,a2,…,an) là một hoán vị của (1,2,…,n).

Dữ liệu ra

In ra số đồ thị nhận hoán vị đã cho là thứ tự DFS, lấy theo modulo 998244353.

Ràng buộc

  • 1≤n≤16
  • (a1,a2,…,an) là một hoán vị của (1,2,…,n).

Ví dụ

Input Output Giải thích
2
2 1
1 Chỉ có một đồ thị là đồ thị đầy đủ (một cạnh 1−2) nhận 2,1 là thứ tự DFS.
3
3 1 2
3 Có 3 đồ thị nhận 3,1,2 là thứ tự DFS: các cạnh {3−1,1−2}, {3−1,3−2} và {3−1,1−2,3−2}.

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