Giúp Chính Mình

Điểm: 1,00 (OI)

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

Python 3 5.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

Cho $N$ đoạn thẳng trên trục số, đoạn $i$ từ $l_{i}$ đến $r_{i}$ . Mọi đầu mút $l_{i}$ , $r_{i}$ đều phân biệt và nằm trong $[1, 2 N]$ .

Với mỗi tập con $S$ của $N$ đoạn, định nghĩa độ phức tạp $c (S)$ là số thành phần liên thông trong hợp của các đoạn trong $S$ (tập rỗng có độ phức tạp 0).

Tính $\sum_{S \subseteq {1, \dots, N}} c (S)^{K} (\mod 10^{9} + 7)$ .

Dữ liệu vào

Dòng 1: hai số nguyên $N$ và $K$ ( $1 \leq N \leq 10^{5}$ , $2 \leq K \leq 10$ )
$N$ dòng tiếp theo: mỗi dòng hai số $l_{i}$ và $r_{i}$ ( $l_{i} < r_{i}$ )

Dữ liệu ra

In ra đáp án modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq N \leq 10^{5}$ , $2 \leq K \leq 10$
Mọi $2 N$ đầu mút đều phân biệt, thuộc $[1, 2 N]$

Ví dụ

Input	Output	Giải thích
3 2 1 6 2 3 4 5	10	Độ phức tạp: $\emptyset = 0$ , ${1} = 1$ , ${2} = 1$ , ${3} = 1$ , ${1, 2} = 1$ , ${1, 3} = 1$ , ${2, 3} = 2$ , ${1, 2, 3} = 1$ . Tổng bình phương: $0 + 1 + 1 + 1 + 1 + 1 + 4 + 1 = 10$ .
16 10 1 27 17 18 10 31 2 26 11 12 23 24 13 14 8 28 9 19 5 6 4 22 15 16 29 30 3 32 20 21 7 25	918764253

Bình luận

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