Bốn Góc Đen · canuc80k2712 · Thuật toán Canuc80k

Cho một bảng vuông $N \times N$ , mỗi ô có màu trắng ( $0$ ) hoặc đen ( $1$ ). Một hình chữ nhật hợp lệ được tạo bởi hai hàng khác nhau và hai cột khác nhau; bốn ô tại giao của hai hàng và hai cột đó đều phải là ô đen. Hãy đếm số hình chữ nhật hợp lệ. Các ô nằm bên trong hoặc trên cạnh còn lại có thể có màu bất kỳ.

Input

Dòng đầu chứa $N$ .
$N$ dòng tiếp theo, mỗi dòng là một chuỗi nhị phân dài đúng $N$ mô tả một hàng của bảng.

Output

In số hình chữ nhật có bốn góc đều đen.

Constraints

$1 \leq N \leq 3000$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 300$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Bốn hình thu được từ các cặp hàng $(1, 2), (1, 4), (2, 3)$ và $(2, 4)$ ; mỗi cặp này có đúng hai cột cùng chứa ô đen.

Mô hình và ý tưởng: Mã hóa mỗi hàng bằng bitset. Với từng cặp hàng, lấy giao để biết các cột cùng có ô đen. Nếu giao có c bit bật thì chọn hai trong số đó theo c(c-1)/2.
Chứng minh tính đúng đắn: Khi cố định hai hàng, các cột có ô đen ở cả hai hàng chính là các bit bật của giao. Chọn bất kỳ hai trong c cột này tạo đúng một hình có bốn góc đen, và mỗi hình xác định duy nhất cặp hàng cùng cặp cột, nên đóng góp là C(c,2) và không trùng.
Độ phức tạp: O(N³/w) thời gian và O(N²/w) bộ nhớ.
Lỗi cài đặt thường gặp: cộng c thay vì C(c,2); đếm cả cặp hàng có thứ tự.