Thoát Hiểm Qua Lá Cây

Buổi 34 — Tree DP & Rerooting Buổi 37 — Convex Hull Trick Buổi 39 — DP + Data Structures Buổi 40 — Contest Chặng 5
Points
88
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Submissions
3\n2 10 10\n10 3 5\n1 2\n1 3 6 0 0
Giới hạn
  • $1 \le N \le 10^5$
  • $-10^5 \le a_i, b_i \le 10^5$
Đề bài

Cho dãy gồm $N$ số nguyên không âm $a_1, a_2, \dots, a_N$ ($0 \le a_i < 2^{20}$). Hãy đếm số lượng cặp chỉ số $(i, j)$ với $1 \le i < j \le N$ sao cho phép AND bit của chúng bằng $0$, tức là $(a_i \mathbin{\&} a_j) = 0$.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$.
  • Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$.
Dữ liệu ra

In ra số lượng cặp $(i, j)$ thỏa mãn.

Draft saved