Hệ phương trình XOR
Points
95
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có $N$ bóng đèn đánh số từ $1$ đến $N$, ban đầu tất cả đều ở trạng thái tắt (0). Có $M$ công tắc đánh số từ $1$ đến $M$; mỗi công tắc $j$ điều khiển một tập hợp các bóng đèn, khi nhấn công tắc $j$ thì trạng thái của tất cả các bóng đèn trong tập này bị đảo ngược (từ 0 thành 1 và ngược lại).
Cho trạng thái mục tiêu của $N$ bóng đèn là một xâu nhị phân độ dài $N$. Hãy đếm số cách chọn một tập con các công tắc để nhấn sao cho sau khi nhấn, trạng thái các bóng đèn khớp với trạng thái mục tiêu. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho $10^9 + 7$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N, M \le 500$).
- $M$ dòng tiếp theo, dòng thứ $j$ bắt đầu bằng số nguyên $k_j$ ($0 \le k_j \le N$) là số lượng bóng đèn mà công tắc $j$ điều khiển, theo sau là $k_j$ số nguyên phân biệt thuộc $[1, N]$ là chỉ số của các bóng đèn đó.
- Dòng cuối cùng chứa xâu nhị phân độ dài $N$ biểu diễn trạng thái mục tiêu của $N$ bóng đèn.
Dữ liệu ra
- Một số nguyên duy nhất là số cách chọn tập công tắc thỏa mãn theo modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 2 2 2 1 2 1 2 11 |
1 |
Giới hạn
- $1 \le N, M \le 500$
Community Discussion