Register | Login

Solutions of XOR pair

Select solution language All Tiếng Việt English Other

Write solution here.

---

minhnhatha    Created at    1 likes

Ta sẽ dùng tính chất: $A_i \oplus j = A_j \oplus i$ ⇒ $A_i \oplus i = A_j \oplus j$ để giải bài này. Lưu số lần xuất hiện XOR rồi tính số cặp có thể tạo ra với XOR đó Độ phức tạp: $O(n.log(n))$ 𝓒𝓸𝓭𝓮 𝓒++ ``` #include <iostream> #include <vector> #include <map> long long tong(long long a){ return a * (a - 1) / 2; } int main(){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int n; unsigned int x; long long dem = 0; std::cin >> n; std::map<unsigned int, long long> f; for (int i = 1; i <= n; ++i) { std::cin >> x; f[x ^ i] ++; } for (std::map<unsigned int, long long>::iterator it = f.begin(); it != f.end(); ++it) dem += tong(it->second); std::cout<<dem; return 0; } ``` ~(Ko thích dùng using namespace std;)~