Tổng Khoảng Cách

Đ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 $K$ đồ thị vô hướng liên thông. Đồ thị thứ $i$ có $N_{i}$ đỉnh và $M_{i}$ cạnh.

Tạo một đồ thị tích $G$ với $N_{1} \cdot N_{2} \dots N_{K}$ đỉnh, mỗi đỉnh là một bộ $K$ -phần tử $(j_{1}, j_{2}, \dots, j_{K})$ . Hai đỉnh $(j_{1}, \dots, j_{K})$ và $(j_{1}^{'}, \dots, j_{K}^{'})$ được nối bằng cạnh trong $G$ khi và chỉ khi tồn tại cạnh $(j_{g}, j_{g}^{'})$ trong đồ thị $g$ với mọi $g = 1, \dots, K$ .

Tính tổng khoảng cách từ đỉnh $(1, 1, \dots, 1)$ đến tất cả các đỉnh có thể đến được trong $G$ , theo modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu tiên chứa $K$ .

Tiếp theo là $K$ nhóm (cách nhau bởi dòng trống), mỗi nhóm mô tả một đồ thị:

Dòng đầu: $N_{i}$ và $M_{i}$
$M_{i}$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $u$ , $v$ là hai đầu của một cạnh

Dữ liệu ra

Một số nguyên duy nhất: tổng khoảng cách theo modulo $10^{9} + 7$ .

Ràng buộc

$2 \leq K \leq 5 \cdot 10^{4}$
$N_{i} \geq 2$ , $M_{i} \geq N_{i} - 1$
$\sum N_{i} \leq 10^{5}$
$\sum M_{i} \leq 2 \cdot 10^{5}$

Ví dụ

Input	Output	Giải thích
2 2 1 1 2 4 4 1 2 2 3 3 4 4 1	4	Đồ thị tích $G$ có 8 đỉnh. Đỉnh $(1, 1)$ đến được $(1, 1)$ , $(1, 2)$ , $(2, 3)$ , $(2, 4)$ với tổng khoảng cách $0 + 1 + 2 + 1 = 4$ .
3 4 4 1 2 2 3 3 1 3 4 6 5 1 2 2 3 3 4 4 5 5 6 7 7 1 2 2 3 3 4 4 5 5 6 6 7 7 1	706

Bình luận

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