Solutions of Cyclic shift

Select solution language

hungkm466 Created at 3 likes

# 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; } ```

TENJOKE Created at 0 likes

Dùng uint32_t để xoay bit dễ hơn bằng công thức sau dịch x sang k bit: $$(x << k) | (x >> (32 - k))$$ Kết hợp với map, mỗi giá trị a[i] thì liệt kê hết tất cả 32 số sau khi dịch bit xem có bao nhiêu số giống a[i] Độ phức tạp : O(n * 32 * log của map) Code : ```cpp #include <bits/stdc++.h> #define foru(i,index_begin,index_end) for (int i=index_begin;i<=index_end;i++) using namespace std; int n; long long ans; map<uint32_t, int> ma; uint32_t rotate(uint32_t x, int k) { return (x << k) | (x >> (32 - k)); } int main() { cin >> n; ans = 0; foru(i,1,n) { uint32_t x; cin >> x; foru(j,0,31) ans += ma[rotate(x, j)]; ma[x]++; } cout << ans; return 0; } //be lan xinh nhat