XOR Problem IV
Xem PDF
Điểm:
1700
Thời gian:
0.6s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho \(N\) xâu nhị phân \(S_1,S_2,\ldots,S_N\).
Mỗi xâu được đánh số từ \(0\) đến \(N-1\).
Xét mọi xâu nhị phân \(T\) có độ dài đúng \(L\).
Định nghĩa
\[
f(T)=
\bigoplus_{\,i:\,S_i\text{ xuất hiện ít nhất một lần trong }T}(1\ll i)
\]
Trong đó \(\oplus\) là phép XOR theo bit.
Nói cách khác, với mỗi mẫu đã xuất hiện ít nhất một lần trong \(T\), ta XOR giá trị \(2^i\). Mỗi mẫu chỉ được tính một lần, dù xuất hiện nhiều lần.
Hãy tính
\[
\sum_{|T|=L} f(T)
\]
Kết quả lấy modulo \(10^9+7\).
Input
- Dòng đầu chứa hai số nguyên \(N, L\).
- \(N\) dòng tiếp theo, dòng thứ \(i\) chứa một xâu nhị phân \(S_i\).
Output
- In ra một số nguyên duy nhất là đáp án.
Constraints
- \(1\le N\le15\)
- \(1\le L\le100\)
- Tổng độ dài các xâu không vượt quá \(300\).
Example
Test
Input
2 2
0
11Output
5Note
Có bốn xâu nhị phân độ dài \(2\):
| \(T\) | Các mẫu xuất hiện | \(f(T)\) |
|---|---|---|
| 00 | \(\{0\}\) | 1 |
| 01 | \(\{0\}\) | 1 |
| 10 | \(\{0\}\) | 1 |
| 11 | \(\{1\}\) | 2 |
Do đó đáp án là \(1+1+1+2=5\).
Bình luận