Doya and XOR#11855

Doya and XOR (Editoryal)

Problem Author:	(De3b0o)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution A number $x$ is divisible by a number $2^{y}$ 2^y , if and only if , all the bits $z < y$ z<y are $0$ in the binary representation of integer $x$ .

For every $y$ ( $1$ to $x$ ) , we only care about the prefix of bits $[0, 1, 2, .., y - 1]$ [0,1,2,..,y-1] for every $a_{i}$ a_i.

Now the answer is just the number of $i \leq j$ i \le j such that $a_{i} \oplus a_{j} = 0$ a_i \oplus a_j = 0 , which means $a_{i} = a_{j}$ a_i = a_j.

We can use a frequency array to maintain frequencies of elements up to $y = 25$ y=25 , then for the last $5$ values of $y$ , we can use a map or any other way to find the answer.

Complexity is $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++