Ba Đỉnh Khép Kín · canuc80k2711

Cho một đồ thị vô hướng đơn gồm $N$ đỉnh, được đánh số từ $1$ đến $N$ . Đồ thị được cho bằng ma trận kề: ký tự thứ $j$ của dòng $i$ bằng $1$ khi có cạnh nối hai đỉnh $i$ và $j$ , và bằng $0$ nếu không có. Hãy đếm số bộ ba đỉnh phân biệt mà mọi cặp đỉnh trong bộ ba đều có cạnh nối.

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$ biểu diễn một hàng của ma trận kề.

Output

In số tam giác của đồ thị.

Constraints

$3 \leq N \leq 3000$ .
Ma trận là đối xứng, mọi phần tử trên đường chéo chính bằng $0$ , và mỗi cặp đỉnh có nhiều nhất một cạnh.

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: Hai tam giác là ${1, 2, 3}$ và ${2, 3, 4}$ . Đỉnh $5$ không nối với đỉnh nào nên không thuộc tam giác.

Mô hình và ý tưởng: Lưu tập láng giềng của mỗi đỉnh bằng bitset. Với từng cạnh (i,j) và i<j, popcount của adj[i] & adj[j] là số đỉnh thứ ba tạo tam giác với cạnh đó. Tổng này đếm mỗi tam giác qua ba cạnh nên chia cho 3.
Chứng minh tính đúng đắn: Với một cạnh i-j, bit k nằm trong adj[i]&adj[j] đúng khi tồn tại cả hai cạnh i-k và j-k, tức ba đỉnh tạo tam giác. Mỗi tam giác được gặp qua đúng ba cạnh của nó trong vòng lặp i<j, nên tổng chia 3 là số tam giác.
Độ 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: chia cho 6 thay vì 3; không kiểm tra cạnh i-j.