TLEoj Cup Final Day 1 - Cặp số độc lập
Xem PDF
Nộp bài
Điểm:
1800 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
IPN.inp
Output:
IPN.out
Tác giả:
Dạng bài
Một cặp số nguyên dương (i, j) được gọi là độc lập với nhau khi và chỉ khi i\ \&\ j = 0, trong đó \& là phép toán thao tác bit AND.
Bạn được cho một dãy số nguyên dương a. Nhiệm vụ của bạn là đếm xem trong dãy có bao nhiêu cặp số độc lập.
Input, Output và Subtask
Input (IPN.inp)
- Dòng đầu tiên gồm một số nguyên dương n - số phần tử của dãy (n \le 10^5).
- Dòng tiếp theo gồm n số nguyên dương a_i là các giá trị của dãy (a_i \le 10^9).
Output (IPN.out)
- Một dòng duy nhất là số cặp số độc lập trong dãy.
Subtask
- 30\% số điểm có n \le 10^4.
- 30\% số điểm khác có a_i \le 10^4.
- 40\% số điểm còn lại không có giới hạn gì thêm.
Sample 1
Input (IPN.inp)
8
1 2 3 4 5 6 7 8
Output (IPN.out)
13
Notes
Các cặp số độc lập là (x, 8) với mọi x < 8, (x, 4) với mọi x < 4, (1, 2), (2, 5), (1, 6)
Bình luận đầu tiên
Bình luận