# Hướng dẫn
Đề bài yêu cầu gì ta làm thứ đó.
Đối với bài này ta có thể sử dụng **Kĩ thuật sinh** kết hợp với **Đếm phân phối - map**.\
Với mỗi số nguyên a[i], ta "xoay vòng" các bit từ phải qua trái theo quy luật đề bài.\
Vì 0 ≤ a[i] < 2^32 nên chỉ có tối đa 32 bit.\
Cách "xoay vòng" tuỳ cách nghĩ sáng tạo của mỗi người.
Ví dụ một cách "xoay vòng" sau:
- Nếu bit 31 bật: Tắt bit 31, dịch tất cả bit sang trái 1 lần, bật bit cuối cùng.
- Nếu bit 31 tắt: Dịch tất cả bit sang trái 1 lần
**Code:** O(32 * n * logn)
```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,a,b) for (int (i)=(a); (i)<=(b); ++(i))
const int MAXN = 1e5 + 5;
const ll cur = INT_MAX + 1ll; // = 2^31
int n;
unordered_map<ll,ll> mp;
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
ll res = 0;
FOR(i,1,n)
{
ll x, old; cin >> x;
old = x;
do
{
if (x & cur)
x = ((x - cur) << 1ll) + 1; // Dich bit sang trai
else
x <<= 1ll; // Dich bit sang phai
res += mp[x];
} while (x != old);
++mp[x];
}
return cout << res,0;
}
```
hungkm466
Created at
1 likes