trang chủ / đề bài / icpc22_nat_e

Xây dựng lãnh địa

Đề bài

Mô tả

Thục đã chơi Age of Empires 2 được vài tháng. Trong trò chơi này, Thục đóng vai nhà vua, ra lệnh cho dân làng xây dựng các lãnh địa cho vương quốc. Khu vực chơi được biểu diễn bằng một bảng kích thước 109×109, trong đó giao của hàng thứ i và cột thứ j được ký hiệu là ô (i,j).

Trong trò chơi, giá trị tài nguyên của mỗi ô (i,j) là (i×j)k, trong đó k là một tham số nguyên dương được cho khi bắt đầu trò chơi.

Thục đã lên kế hoạch xây n lãnh địa trên khu vực chơi để thu tài nguyên. Lãnh địa thứ i được biểu diễn bằng một hình chữ nhật với tọa độ xi,1,yi,1,xi,2,yi,2 (1≤xi,1≤xi,2≤109, 1≤yi,1≤yi,2≤109), nghĩa là Thục sẽ chiếm mọi ô (x,y) thỏa mãn xi,1≤x≤xi,2 và yi,1≤y≤yi,2. Trò chơi không giới hạn việc xây dựng, vì vậy các lãnh địa có thể có chung một số ô.

Đáng tiếc, hôm nay Thục phát hiện ra rằng tài nguyên của một ô không thể được thu quá một lần, nên cách tính tổng tài nguyên của Thục không còn đúng nữa. Hãy giúp Thục tính lại tổng giá trị tài nguyên thực sự mà Thục thu được theo kế hoạch.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và k: số lãnh địa trong kế hoạch và tham số k.
  • Dòng thứ i trong n dòng tiếp theo chứa bốn số nguyên xi,1,yi,1,xi,2,yi,2 là tọa độ của lãnh địa thứ i.

Dữ liệu ra

In ra một số nguyên là tổng giá trị tài nguyên thực sự Thục thu được, lấy theo modulo 109+7.

Ràng buộc

  • 1≤n≤2·105, 1≤k≤20.
  • 1≤xi,1≤xi,2≤109, 1≤yi,1≤yi,2≤109.

Ví dụ

Input Output Giải thích
2 2
1 1 2 2
1 2 1 3
34 Các ô bị chiếm là (1,1), (1,2), (2,1), (2,2), (1,3) với giá trị 1+4+4+16+9=34. Hai lãnh địa có chung ô (1,2), ô này chỉ được tính một lần.
3 3
1 1 1 1
1 1 1 1
2 2 3 3
1226 Ví dụ bổ sung: hai lãnh địa đầu trùng nhau, chỉ gồm ô (1,1) (giá trị 1). Lãnh địa thứ ba gồm các ô (2,2), (2,3), (3,2), (3,3) với giá trị 43+63+63+93=1225, tổng cộng 1+1225=1226.

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