Gọi $\texttt{cnt}[i] \ (0 \leq i \leq n)$ là số ma trận nhị phân có **ít nhất** $i$ hàng không chứa số $1$ và mọi cột đều chứa số 1.
Sử dụng bao hàm loại trừ, số ma trận thỏa mãn đề bài là:
$$
\sum_{i = 0}^n (-1)^i\times \texttt{cnt}[i]
$$
Để tính $\texttt{cnt}[i]$ ta mô phỏng lại quá trình xây dựng bảng theo các bước sau:
- Chọn $i$ hàng không chứa số $1$: Có $\binom{n}{i}$ cách chọn.
- Điền số vào các ô còn lại: Sau khi cố đỉnh $i$ hàng, mỗi cột còn $n - i$ ô có thể điền vào. Vì mỗi cột cần chứa ít nhất một số $1$ và có $m$ cột nên số cách điền số vào các ô còn lại là $(2^{n - 1} - 1)^m$
Theo quy tắc nhân, ta thu được:
$$
\texttt{cnt}[i] = \binom{n}{i}\times (2^{n - 1} - 1)^m
$$
Độ phức tạp của thuật toán là $O(n)$ (không phù hợp với giới hạn $n \times m \leq 10^9$). Cách tối ưu khá đơn giản, do bảng $n \times m$ và bảng $m \times n$ là tương đương nhau nên ta có thể đảo lại sao cho $n \leq m$ để có độ phức tạp $O(\min(n, m))$.
Cách làm trên đủ nhanh vì $\min(n,m)^2 \leq n\times m \leq 10^9 \Rightarrow \min(n,m) \leq \sqrt{10^9}\approx 3\times 10^4$.
## Nhận xét
- Ta thấy $n \times m \le 10^9$. Ta giả sử $n \le m \Rightarrow n^2 \le n \times m \le 10^9 \Rightarrow n \le \sqrt{10^9}$
- Từ đó ta có thể giải quyết bài toán này với độ phức tạp $O(n \log n)$ bằng cách khi thấy $n > m$ thì `swap(n, m)` lại
- Ta nhận thấy nếu bài toán chỉ yêu cầu tính số lượng hàng có **ít nhất một số $1$** thì mọi chuyện sẽ **đơn giản** hơn nhiều.
- Nên thay vì ta phải kiểm soát **điều kiện của cả hàng với cột** thì ta sẽ phải kiểm soát (fix) hàng.
- Bằng cách giả sử có ít nhất $i$ hàng toàn $0$ thì có bao nhiêu bảng thoả mãn
## Tính số lượng bảng $n \times m$ thoả mãn mọi cột đều tồn tại ít nhất một số $1$
- Số lượng cấu hình cột gồm $n$ ô: $2^n$
- Số lượng cấu hình cột gồm $n$ ô mà tồn tại **ít nhất một số $1$**: $2^n - 1$
- Số lượng bảng thoả mãn mà mọi cột đều có ít nhất một số $1$: $(2^n - 1)^m$
## Thuật toán
- Gọi $f(x)$ là số lượng bảng thoả mãn mọi cột đều tồn tại ít nhất một số $1$ mà có $x$ hàng toàn 0
- Thì ta chỉ cần quy về bài toán tương tự với bảng có kích thước $(n - x) \times m$
- Và ta cũng đếm xem có bao nhiêu cách chọn $x$ hàng qua công thức tính tổ hợp $C^x_n$
- Cuối cùng, ta áp dụng bao hàm loại trừ và nghiệm của bài toán bằng:
$$
\sum^n_{i = 0} C^i_n \times f(i)
$$
chithanhnguyen
Created at
0 likes