Соломія та Леся і XOR#11855

Соломія та Леся і XOR (Розбір)

Автор задачі:	(De3b0o)
Підготовлено:	Hasan Saleh (MathModel)
Редаговано:	Hasan Saleh (MathModel)

Рішення Число $x$ ділиться на число $2^{y}$ 2^y, якщо і тільки якщо всі біти $z < y$ z<y дорівнюють $0$ у двійковому представленні цілого числа $x$ .

Для кожного $y$ ( $1$ до $x$ ), нас цікавить лише префікс бітів $[0, 1, 2, .., y - 1]$ [0,1,2,..,y-1] для кожного $a_{i}$ a_i.

Тепер відповідь - це просто кількість $i \leq j$ i \le j таких, що $a_{i} \oplus a_{j} = 0$ a_i \oplus a_j = 0, що означає $a_{i} = a_{j}$ a_i = a_j.

Ми можемо використовувати масив частот для підтримки частот елементів до $y = 25$ y=25, а потім для останніх $5$ значень $y$ ми можемо використовувати мапу або будь-який інший спосіб, щоб знайти відповідь, але це не обов'язково для проходження задачі.

Складність становить $O (x \cdot n lo g n)$ \mathcal{O}(x \cdot n \log n) або $O (x \cdot n + 5 \cdot n lo g n)$ \mathcal{O}(x \cdot n + 5 \cdot n \log n) в залежності від вашої реалізації.

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)
 
using namespace std;

const int N = 2e5+9;

int t , n;
int16_t x;
int a[N];
bool lg[N][35];
int frq[50000000];
vector<int> v;
int po;

int main()
{
    d3
    cin >> t;
    while(t--)
    {
        cin >> n >> x;
        for(int i = 1 ; n>=i ; i++)
        {
            cin >> a[i];
            po=1;
            for(int j = 0 ; x>j ; j++)
            {
                lg[i][j]=0;
                if(a[i]&po)
                    lg[i][j]=1;
                po*=2;
            }
            a[i]=0;
        }
        po=1;
        for(int i = 1 ; x>=i ; i++)
        {
            ll ans;
            if(i<25)
            {
                for(int j = 1 ; n>=j ; j++)
                    a[j]+=po*lg[j][i-1],frq[a[j]]++;
                ans = 0;
                for(int j = 1 ; n>=j ; j++)
                    ans+=frq[a[j]]+1;
                for(int j = 1 ; n>=j ; j++)
                    frq[a[j]]=0;
                ans/=2;
            }
            else
            {
                v.clear();
                for(int j = 1 ; n>=j ; j++)
                    a[j]+=po*lg[j][i-1],v.pb(a[j]);
                sort(v.begin(),v.end());
                ans = 1;
                ll c = 1;
                for(int j = 1 ; n>j ; j++)
                {
                    if(v[j]==v[j-1])
                        c++;
                    else
                        c=1;
                    ans+=c;
                }
            }
            cout << ans << " ";
            po*=2;
        }
        lin
    }
}

C++