Cơn Ác Mộng Euclid

Điểm: 7,00 (OI)

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

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một tập $S$ gồm $n$ vectơ trên trường $ℤ_{2}$ với $m$ chiều. Mỗi vectơ có $m$ tọa độ, mỗi tọa độ bằng $0$ hoặc $1$ . Phép cộng hai vectơ $u + v = w$ được định nghĩa $w_{i} = (u_{i} + v_{i}) mod 2$ .

Bạn được cộng tùy ý một tập con của $S$ (kể cả tập rỗng — kết quả là vectơ $0$ ). Gọi $T$ là tập tất cả các vectơ có thể tạo được bằng cách cộng một tập con nào đó của $S$ .

Mỗi vectơ trong $S$ có không quá 2 tọa độ bằng 1.

Hãy tính:

$| T |$ theo modulo $10^{9} + 7$ .
Một tập con $S^{'} \subseteq S$ có kích thước nhỏ nhất sao cho mọi vectơ trong $T$ vẫn có thể tạo được bằng cách cộng các vectơ trong $S^{'}$ .

Nếu có nhiều tập $S^{'}$ kích thước nhỏ nhất, hãy chọn tập có dãy chỉ số nhỏ nhất theo thứ tự từ điển. So sánh hai tập có cùng kích thước: viết các chỉ số phần tử theo thứ tự tăng dần thành dãy $a_{1} < a_{2} < \dots$ và $b_{1} < b_{2} < \dots$ ; $A$ nhỏ hơn $B$ về thứ tự từ điển nếu tồn tại $i$ sao cho $a_{j} = b_{j}$ với mọi $j < i$ và $a_{i} < b_{i}$ .

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ , $m$ .
$n$ dòng tiếp theo mô tả các vectơ. Mỗi dòng bắt đầu bằng số nguyên $k$ ( $1 \leq k \leq 2$ ), tiếp theo là $k$ số nguyên phân biệt $x_{1}, \dots, x_{k}$ ( $1 \leq x_{i} \leq m$ ), biểu diễn vectơ có giá trị $1$ tại các tọa độ $x_{1}, \dots, x_{k}$ và $0$ ở các vị trí còn lại.

Không có hai vectơ nào trong $S$ trùng nhau.

Dữ liệu ra

Dòng đầu tiên in hai số: $| T | mod (10^{9} + 7)$ và $| S^{'} |$ .
Dòng thứ hai in $| S^{'} |$ chỉ số của các phần tử trong $S^{'}$ theo thứ tự tăng dần (đánh số từ $1$ theo thứ tự đầu vào).

Ràng buộc

$1 \leq n, m \leq 5 \cdot 10^{5}$ .
$1 \leq k \leq 2$ .
$1 \leq x_{i} \leq m$ .

Ví dụ

Input	Output	Giải thích
3 2 1 1 1 2 2 2 1	4 2 1 2	Ba vectơ là $10$ , $01$ , $11$ . Vì $11 = 10 + 01$ , vectơ thứ ba phụ thuộc vào hai vectơ đầu. Không gian sinh có $4$ phần tử. Chọn $S^{'} = {1, 2}$ — kích thước tối thiểu, thứ tự từ điển nhỏ nhất.
2 3 2 1 3 2 1 2	4 2 1 2	Hai vectơ $101$ và $110$ đều độc lập, sinh ra không gian $4$ phần tử.
3 5 2 1 2 1 3 1 4	8 3 1 2 3	Ba vectơ độc lập, sinh ra không gian $2^{3} = 8$ phần tử. Chỉ số $S^{'} = {1, 2, 3}$ .

Bình luận

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