trang chủ / đề bài / icpc24_nat_b

Bản quy hoạch đại lộ

Đề bài

Mô tả

Một khu đô thị mới quy hoạch ở thành phố Hà Nội có bố cục rất đẹp. Khu đô thị có dạng hình chữ nhật kích thước w×h, góc dưới bên trái ở điểm (0,0) và góc trên bên phải ở điểm (w,h). Khu đô thị có w+1 đại lộ dọc cách đều nhau tại x=0,x=1,x=2,…,x=w và h+1 đại lộ ngang cách đều nhau tại y=0,y=1,y=2,…,y=h.

Ban quản lý khu đô thị muốn gán chiều cho gần như tất cả các đại lộ, cho phép tối đa một đại lộ được giữ hai chiều để giảm ùn tắc. Mỗi đại lộ dọc (một chiều) đi theo hướng Bắc xuống Nam hoặc Nam lên Bắc, mỗi đại lộ ngang (một chiều) đi theo hướng Tây sang Đông hoặc Đông sang Tây.

Có n yêu cầu di chuyển ưu tiên, yêu cầu thứ j (1≤j≤n) nối hai địa điểm (uj,vj) và (pj,qj). Yêu cầu này được thỏa mãn nếu cả hai điều kiện sau cùng đúng:

  • Có thể đi từ (uj,vj) đến (pj,qj) với tối đa một lần rẽ.
  • Có thể đi từ (pj,qj) đến (uj,vj) với tối đa một lần rẽ.

Một lần rẽ là việc chuyển hướng di chuyển từ một đại lộ dọc sang một đại lộ ngang, hoặc từ một đại lộ ngang sang một đại lộ dọc.

Hãy đếm số cách đặt chiều cho các đại lộ sao cho mọi yêu cầu đều được thỏa mãn, trong khi có tối đa một đại lộ hai chiều. Hai cách được coi là khác nhau nếu có ít nhất một đại lộ được gán chiều khác nhau (giữ hai chiều cũng là một lựa chọn chiều). Vì kết quả có thể rất lớn, chỉ cần in ra số dư của nó khi chia cho 998244353.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương t (t≤105): số bộ test. Tiếp theo là t bộ test, mỗi bộ có dạng:

  • Dòng đầu tiên chứa ba số nguyên dương w, h và n (1≤w,h≤2·105, 1≤n≤105): chiều rộng, chiều cao của khu đô thị và số yêu cầu ưu tiên.
  • Dòng thứ j trong n dòng tiếp theo chứa bốn số nguyên uj,vj,pj,qj (0≤uj,pj≤w, 0≤vj,qj≤h): yêu cầu ưu tiên thứ j.

Dữ liệu đảm bảo:

  • tổng w trên tất cả các bộ test không vượt quá 2·105,
  • tổng h trên tất cả các bộ test không vượt quá 2·105,
  • tổng n trên tất cả các bộ test không vượt quá 105.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng chứa số cách đặt chiều cho các đại lộ, lấy dư khi chia cho 998244353.

Ràng buộc

  • 1≤t≤105
  • 1≤w,h≤2·105, 1≤n≤105
  • 0≤uj,pj≤w, 0≤vj,qj≤h
  • Tổng w, tổng h trên tất cả các bộ test đều không vượt quá 2·105; tổng n không vượt quá 105.

Ví dụ

Input Output Giải thích
4
2 2 2
0 0 1 1
0 1 1 2
1 2 2
0 0 1 2
0 0 1 1
2 2 2
0 0 1 1
1 1 2 2
2 2 3
0 0 1 1
0 0 2 2
1 1 2 2
4
12
14
0
Bộ test thứ tư: dù chọn đại lộ hai chiều nào, ba yêu cầu cũng không thể cùng được thỏa mãn.
3
1 1 1
0 0 0 1
3 1 2
0 0 3 1
2 1 1 0
1 1 2
0 0 0 1
0 0 1 0
8
14
0
Bộ test thứ nhất: hai điểm cùng nằm trên đại lộ x=0 nên đại lộ này phải là đại lộ hai chiều, ba đại lộ còn lại tùy ý: 23=8 cách. Bộ test thứ ba: cả đại lộ x=0 và y=0 đều phải là hai chiều, không thể.

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