Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

HackerEarth Boring Not boring problem solution

YASH PAL, 31 July 2024
In this HackerEarth Boring Not boring problem solution You are given two integers n(1 <= n <= 10^5) and m(1 <= m <= 10^5). Initially, you have an array a of n zeros, and m applied queries on it. Query is given as l r x, where you apply ai = ai xor x (xor denotes the operation bitwise XOR) for every i between l and r. But this problem seems boring, so Almas modify some queries interval. By modifying, he applied that operation on a subset of positions on a segment(maybe an empty subset). Now he asks you how many different arrays he could have after applying queries. Since the answer can be large, output by modulo 1000000007 (10^9 + 7).
HackerEarth Boring Not boring problem solution

HackerEarth Boring Not boring problem solution.

# include <bits/stdc++.h>

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y) for (ll i = x; i <= y; i ++)
#define FOr(i,x,y) for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)


void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 1e5+5;
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

int rnd (int l, int r) {
return uniform_int_distribution<int> (l, r)(gen);
}

int n, m;

vector < int > g[N*4];

struct GG {
//gauss
vector < int > basis;
void add(int x) {
for(auto &it:basis) if((x^it)<x) x^=it;
for(auto &it:basis) if((it^x)<it) it^=x;
if(x) basis.pb(x);
}

int get() {
int ans = 0;
for (auto x:basis) ans ^= x;
return ans;
}

void clear() {
basis.clear();
}
};

void add(int l, int r, int x, int v=1, int tl = 1, int tr =n) {
if(tl>r || l > tr) return;
if(tl >= l && tr <= r) {
g[v].pb(x);
return;
}

int tm = (tl+tr)>>1;
add(l, r, x, v<<1, tl, tm);
add(l, r, x, v<<1|1, tm+1, tr);
}

int pw[33];

int calc(GG c, int v, int l, int r) {
for (auto x : g[v])
c.add(x);

if(l == r) {
return pw[c.basis.size()];
}

int md = (l+r)>>1;
return calc(c, v<<1, l, md)
* (ll)calc(c, v<<1|1, md+1, r) % mod;
}

void solve() {
cin >> n >> m;

for (int i = 1, l, r, x; i <= m; ++i) {
cin >> l >> r >> x;
add(l, r, x);
}

GG c;
cout << calc(c, 1, 1, n) << 'n';
}

int main () {
SpeedForce;
pw[0] = 1;

for (int i = 1; i < 33; ++i) {
pw[i] = (pw[i-1] * 2) % mod;
}

int T = 1;
//cin >> T;
while(T--) solve();

return Accepted;
}

Second solution

#include <bits/stdc++.h>


using namespace std;
typedef long long ll;

const int MAX_N = 1e5 + 14, LG = 30, MOD = 1000000007;

struct Gauss {
int a[LG];

Gauss() {
memset(a, 0, sizeof a);
}

void add(int x) {
for (int i = LG - 1; i >= 0; i--)
if (x >> i & 1)
if (a[i])
x ^= a[i];
else {
a[i] = x;
break;
}
}

void operator+=(vector<int> &o) {
for (int i : o)
if (i)
add(i);
}

int cnt() {
return 1 << LG - count(a, a + LG, 0);
}
};

vector<int> node[1 << 18];
int n;

void add(int s, int e, int x, int l = 0, int r = n, int id = 1) {
if (s <= l && r <= e) {
node[id].push_back(x);
return;
}
if (e <= l || r <= s)
return;
int mid = (l + r) / 2;
add(s, e, x, l, mid, id * 2);
add(s, e, x, mid, r, id * 2 + 1);
}

int get_ans(int l = 0, int r = n, int id = 1, Gauss carry = Gauss()) {
carry += node[id];
if (l + 1 == r)
return carry.cnt();
int mid = (l + r) / 2;
return (ll) get_ans(l, mid, id * 2, carry) * get_ans(mid, r, id * 2 + 1, carry) % MOD;
}

int main() {
ios::sync_with_stdio(0), cin.tie(0);
int m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int l, r, x;
cin >> l >> r >> x;
add(l - 1, r, x);
}
cout << get_ans() << 'n';
}
coding problems

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes