HackerEarth Utkarsh and Sub Array Xor problem solution

In this HackerEarth Utkarsh and Sub Array Xor problem solution, Utkarsh loves binary sequences. Once he was playing with his favorite binary sequence of length N. But somehow he misplaced it. He remembers the bitwise XOR of exactly K subarrays. Utkarsh fears that you will steal his sequence so he will not reveal the actual XOR value of any sub-array.

He plans to recover the sequence using this information only. You being his best friend will convince him there are just too many sequences satisfying the Sub Array Xor and it’s better to forget his love for that sequence.

HackerEarth Utkarsh and Sub Array Xor problem solution.

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define fre     freopen("0.in","r",stdin);freopen("0.out","w",stdout)
#define abs(x) ((x)>0?(x):-(x))
#define MOD 1000000007
#define lld signed long long int
#define pii pair<int,int>
#define scan(x) scanf("%d",&x)
#define print(x) printf("%dn",x)
#define scanll(x) scanf("%lld",&x)
#define printll(x) printf("%lldn",x)
vector<int> G[2*100000+5];
#define DSU_SZ 2000000

lld pow(lld base, lld exponent,lld modulus)
{
    lld result = 1;
    while (exponent > 0)
    {
        if (exponent % 2 == 1)
            result = (result * base) % modulus;
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}
lld N;
int n,dad[DSU_SZ+5],rnk[DSU_SZ+5];
struct DSU
{
    void init(int nn)
    {
        n = nn;
        for (int i = 1; i <=n; i++)
        {
            rnk[i] = 0;
            dad[i] = i;
        }
    }
    int root(int v)
    {
        if (v == dad[v]) return v;
        return dad[v] = root(dad[v]);
    }
    void join(int v1, int v2)
    {
        v1 = root(v1), v2 = root(v2);
        if (v1 == v2) return;
        if (rnk[v1] < rnk[v2]) swap(v1, v2);
        dad[v2] = v1;
        N--;
        if (rnk[v1] == rnk[v2]) rnk[v1]++;
    }
};
vector<pair<lld,lld> >E;
map<lld,lld>mp;
vector<lld>V;
int main(){
    int K;
    lld a,b;
    cin>>N>>K;
    for(int i=1;i<=K;++i){
        scanll(a);
        scanll(b);
        a--;
        E.push_back(make_pair(a,b));
        V.push_back(a);
        V.push_back(b);
    }
    sort(V.begin(),V.end());
    for(int i=0;i<V.size();++i){
        mp[V[i]] = i+1;
    }
    DSU dsu;
    dsu.init(V.size());
    for(int i=0;i<E.size();++i){
        dsu.join(mp[E[i].first],mp[E[i].second]);
        printll(pow(2,N,MOD));
    }
}

Second solution

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1E9 + 7;

long long bin(long long x, long long y) {
    if (y == 0) {
        return 1;
    }
    long long u = bin(x, y/2);
    if (y%2 == 0) {
        return u*u % MOD;
    }
    else {
        return u*u*x % MOD;
    }
}

unordered_map<long long, long long> pr;
long long n;

long long dsuFind(long long x) {
    if (pr.find(x) == pr.end() || pr[x] == x) {
        return x;
    }
    long long res = dsuFind(pr[x]);
    pr[x] = res;
    return res;
}

void dsuUnite(long long u, long long v) {
    long long A = dsuFind(u), B = dsuFind(v);
    if (rand() % 2 ) {
        pr[A] = B;
    }
    else {
        pr[B] = A;
    }
}

int main(){
    cin>>n;
    assert(1 <= n && n <= (long long)1E9 * (long long)1E6);
    int k;
    cin>>k;
    assert(k <= 1E6);
    assert(k <= (long long)n*(n - 1)/2 );
    long long ans = bin(2, n);
    for (int i = 0; i < k; i++) {
        long long u, v;
        cin>>u>>v;
        assert(u <= v);
        assert(1 <= u && u <= n);
        assert(1 <= v && v <= n);
        u--;
        if (dsuFind(u) != dsuFind(v) ) {
            ans = ans * bin(2, MOD - 2) % MOD;
            dsuUnite(u, v);
        }
        cout<<ans<<endl;
    }
    return 0;
}

coding problems solutions