Solutions of XOR pair

Select solution language

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;)~

Sherwin Created at 0 likes

Ta biến đổi công thức: A[i] ^ j = A[j] ^ i -> A[i] ^ j ^ (i ^ j) = A[j] ^ i ^ (i ^ j) -> A[i] ^ i ^ (j ^ j) = A[j] ^ j ^ (i ^ i) -> A[i] ^ i ^ 0 = A[j] ^ j ^ 0 -> A[i] ^ i = A[j] ^ j __=> Vậy với 1 giá trị là hợp lệ ta cần đếm số cặp phân biệt với (i != j) và cặp (i, j) cũng đc coi là (j, i)__ Code Mẫu: #include <bits/stdc++.h> using namespace std; constexpr int mx = 1e5; int A[mx + 5]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; for (int i = 1; i <= n; ++i){ cin >> A[i]; A[i] ^= i; } sort(A + 1, A + n + 1); A[n + 1] = -1; int cnt = 1; int ans = 0; for (int i = 1; i <= n; ++i) if (A[i] == A[i + 1]) ++cnt; else{ ans += (cnt - 1)*cnt/2; cnt = 1; } cout << ans; }