Nhân Bản Hóa Học

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bác sĩ hóa học Bessie đang nghiên cứu $N$ hộp hóa chất. Hộp thứ $i$ chứa các hóa chất được đánh nhãn từ $l_{i}$ đến $r_{i}$ (mỗi nhãn là một số nguyên). Các hộp không giao nhau và được sắp xếp theo thứ tự tăng dần (tức là $r_{i} < l_{i + 1}$ với mọi $i$ ).

Một hỗn hợp gồm 3 hóa chất khác nhau ${x, y, z}$ được gọi là hợp lệ nếu tất cả các XOR từng cặp đều không vượt quá $K$ , tức là:

$x \oplus y \leq K, x \oplus z \leq K, y \oplus z \leq K$

Đếm số lượng bộ ba hóa chất hợp lệ (không phân biệt thứ tự), lấy phần dư cho $10^{9} + 7$ .

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $K$ .
$N$ dòng tiếp theo, dòng thứ $i$ gồm hai số nguyên $l_{i}$ và $r_{i}$ .

Dữ liệu ra

Một số nguyên duy nhất là số lượng bộ ba hợp lệ modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq N \leq 2 \times 10^{4}$
$0 \leq K \leq 10^{9}$
$0 \leq l_{i} \leq r_{i} \leq 10^{9}$
Các hộp không giao nhau và được sắp theo thứ tự: $r_{i} < l_{i + 1}$

Ví dụ

Input	Output	Giải thích
1 13 0 199	4280	$N = 1$ hộp chứa 200 hóa chất nhãn $0$ đến $199$ . Đếm tất cả bộ ba ${x, y, z}$ với $x, y, z \in [0, 199]$ và tất cả XOR từng cặp $\leq 13$ .
6 147 1 35 48 103 125 127 154 190 195 235 240 250	267188	$N = 6$ hộp với tổng cộng $175$ hóa chất.

Ghi chú

Ba hóa chất $x, y, z$ phải khác nhau (khác nhãn).
Hóa chất trong các hộp khác nhau có nhãn khác nhau (do hộp không giao nhau).
Bộ ba ${x, y, z}$ không phân biệt thứ tự, tức là ${1, 2, 3}$ và ${3, 1, 2}$ được coi là một.

Bình luận

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