Doya y XOR#11855

Doya y XOR (Editorial)

Autor del Problema:	(De3b0o)
Preparado por:	Hasan Saleh (MathModel)
Editado por:	Hasan Saleh (MathModel)

Solución Un número $x$ es divisible por un número $2^{y}$ 2^y, si y solo si, todos los bits $z < y$ z<y son $0$ en la representación binaria del entero $x$ .

Para cada $y$ ( $1$ a $x$ ), solo nos importa el prefijo de bits $[0, 1, 2, .., y - 1]$ [0,1,2,..,y-1] para cada $a_{i}$ a_i.

Ahora la respuesta es solo el número de $i \leq j$ i \le j tales que $a_{i} \oplus a_{j} = 0$ a_i \oplus a_j = 0, lo que significa que $a_{i} = a_{j}$ a_i = a_j.

Podemos usar un arreglo de frecuencias para mantener las frecuencias de los elementos hasta $y = 25$ y=25, luego para los últimos $5$ valores de $y$ , podemos usar un mapa o cualquier otro método para encontrar la respuesta, pero no es necesario para resolver el problema.

La complejidad es $O (x \cdot n lo g n)$ \mathcal{O}(x \cdot n \log n) o $O (x \cdot n + 5 \cdot n lo g n)$ \mathcal{O}(x \cdot n + 5 \cdot n \log n) dependiendo de tu implementació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++