Doya və XOR#11855

Doya və XOR (Həll təhlili)

Problem Müəllifi:	(De3b0o)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll Bir ədəd $x$ $2^{y}$ 2^y ədədinə tam bölünür, yalnız o zaman ki, bütün bitlər $z < y$ z<y tam ədəd $x$ -in ikili təqdimatında $0$ -dır.

Hər $y$ ( $1$ -dən $x$ -ə) üçün, yalnız $a_{i}$ a_i üçün bitlərin $[0, 1, 2, .., y - 1]$ [0,1,2,..,y-1] prefiksinə diqqət edirik.

İndi cavab sadəcə $i \leq j$ i \le j sayıdır ki, $a_{i} \oplus a_{j} = 0$ a_i \oplus a_j = 0 , bu da deməkdir ki, $a_{i} = a_{j}$ a_i = a_j.

Biz $y = 25$ y=25-ə qədər elementlərin tezliklərini saxlamaq üçün bir tezlik massivi istifadə edə bilərik, sonra $y$ -nin son $5$ dəyəri üçün, cavabı tapmaq üçün bir xəritə və ya başqa bir yol istifadə edə bilərik, amma problemi keçmək üçün bu zəruri deyil.

Komplekslik $O (x \cdot n lo g n)$ \mathcal{O}(x \cdot n \log n) və ya $O (x \cdot n + 5 \cdot n lo g n)$ \mathcal{O}(x \cdot n + 5 \cdot n \log n) sizin tətbiqinizdən asılıdır.

#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 << "BƏLİ" << "\n";
#define no cout << "XAHŞI" << "\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++