Doya et XOR#11855

Doya et XOR (Corrigé)

Auteur du problème:	(De3b0o)
Préparé par:	Hasan Saleh (MathModel)
Édité par:	Hasan Saleh (MathModel)

Solution Un nombre $x$ est divisible par un nombre $2^{y}$ 2^y, si et seulement si, tous les bits $z < y$ z<y sont $0$ dans la représentation binaire de l'entier $x$ .

Pour chaque $y$ ( $1$ à $x$ ), nous ne nous soucions que du préfixe de bits $[0, 1, 2, .., y - 1]$ [0,1,2,..,y-1] pour chaque $a_{i}$ a_i.

Maintenant, la réponse est simplement le nombre de $i \leq j$ i \le j tels que $a_{i} \oplus a_{j} = 0$ a_i \oplus a_j = 0, ce qui signifie $a_{i} = a_{j}$ a_i = a_j.

Nous pouvons utiliser un tableau de fréquence pour maintenir les fréquences des éléments jusqu'à $y = 25$ y=25, puis pour les 5 dernières valeurs de $y$ , nous pouvons utiliser une carte ou tout autre moyen pour trouver la réponse, mais ce n'est pas nécessaire pour résoudre le problème.

La complexité est $O (x \cdot n lo g n)$ \mathcal{O}(x \cdot n \log n) ou $O (x \cdot n + 5 \cdot n lo g n)$ \mathcal{O}(x \cdot n + 5 \cdot n \log n) selon votre implémentation.

#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 << "OUI" << "\n";
#define no cout << "NON" << "\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++