trang chủ / đề bài / icpc21_reg_c

Tô màu đa giác

Đề bài

Mô tả

Cho một đa giác lồi có n đỉnh, các đỉnh được đánh số từ 1 đến n theo chiều kim đồng hồ. Một đường chéo là một đoạn thẳng nối hai đỉnh không kề nhau của đa giác. Nói cách khác, một đường chéo nối hai đỉnh u và v của đa giác với |u−v|∉{1,n−1}.

Bài toán gồm hai bước:

  1. Đầu tiên, bạn cần chia đa giác thành n−2 tam giác bằng n−3 đường chéo. Mỗi cách chia hợp lệ được xác định duy nhất bởi một tập n−3 đường chéo của đa giác sao cho các đường chéo được chọn chỉ cắt nhau tại đầu mút. Nói cách khác, nếu hai đường chéo của một cách chia hợp lệ có điểm chung thì điểm chung đó phải là một đỉnh của đa giác. Cho trước k đường chéo (u1,v1),(u2,v2),…,(uk,vk), bạn cần tìm thêm n−3−k đường chéo khác để tạo thành một cách chia hợp lệ.
  2. Sau đó, bạn cần tô màu cả n−2 tam giác bằng m màu (đánh số từ 1 đến m), sao cho mỗi tam giác được tô đúng một màu và hai tam giác có chung một cạnh phải được tô khác màu.

Với z là một cách chia hợp lệ có thể nhận được ở bước một, gọi f(z) là số cách tô màu các tam giác ở bước hai. Bạn cần tính hai giá trị:

  • P=minf(z), tức là số cách tô màu hợp lệ nhỏ nhất ở bước hai, xét trên mọi cách chia hợp lệ ở bước một.
  • Q là số cách chia hợp lệ z thỏa mãn f(z)=P; nói cách khác, là số cách chia hợp lệ ở bước một cho số cách tô màu nhỏ nhất ở bước hai.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên n, k và m.
  • k dòng tiếp theo, dòng thứ i chứa hai số nguyên ui và vi (1≤ui,vi≤n) mô tả một đường chéo nối hai đỉnh ui và vi của đa giác.

Dữ liệu đảm bảo k đường chéo này chỉ cắt nhau tại đầu mút.

Dữ liệu ra

In ra hai số nguyên trên một dòng: giá trị P và Q. Vì các giá trị này có thể rất lớn, hãy in chúng theo modulo 998244353.

Ràng buộc

  • 3≤n≤105.
  • 0≤k≤n−3.
  • 1≤m≤105.
  • 1≤ui,vi≤n.

Ví dụ

Input Output Giải thích
4 0 2 2 2 Hình vuông có 2 cách chia (theo đường chéo (1,3) hoặc (2,4)), mỗi cách chia cho 2 tam giác kề nhau và có 2 cách tô bằng 2 màu.
6 3 3
2 4
4 6
6 2
24 1 Ba đường chéo đã cho tạo thành cách chia duy nhất gồm 4 tam giác: tam giác (2,4,6) ở giữa kề với ba tam giác còn lại. Tô tam giác giữa có 3 cách, mỗi tam giác còn lại có 2 cách: 3·23=24.

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