PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Practice
Setter: Dinmukhamed Tursynbay
Testers: Takuki Kurokawa and Nishank Suresh
Editorialist: Utkarsh Gupta
DIFFICULTY
2855
PREREQUISITES
XOR, Graph, Combinatorics
PROBLEM
You are given an array A of N integers, initially all zero.
There are Q types of operations that you are allowed to perform. Each operation is described by two integers l_i and r_i (1 \leq l_i \leq r_i \leq N) and is as follows:
- Set A_j = A_j \oplus 1 for each j such that l_i \leq j \leq r_i.
Here \oplus represents the Bitwise XOR operator.
Your task is to find the number of distinct arrays which can be obtained by applying some subset of these operations (possibly none, possibly all). Since the answer may be huge, output it modulo 998244353.
EXPLANATION
Prepend A_0 = 0 and A_{N+1} = 0 to the array A.
Let us construct another array B of length N+1 such that B_i = A_i \oplus A_{i+1}.
We can see that after applying any query [L, R] exactly 2 values in the array B (B_{L-1} and B_R) will change. So for each query [L, R] we will add an edge between the nodes L-1 and R as values of both B_{L-1} and B_R will get changed after this operation.
There might be more than one components in the graph. It is easy to see that each component is different since the nodes concerned will be disjoint. So we will compute answer for all the components individually and multiply them to obtain the final answer.
Calculating Answer for one component
Consider a cycle in the component. If we apply operation on all the edges of a cycle then it will reset the values of all the nodes involved in the cycle. So we can remove the edges involved in the cycle and obtain a spanning tree. Now we can see the each edge is independent (i.e. changing the state of any edge will give us a new array). Let the number of nodes in the component be X. So there will be total X-1 edges (Since we have obtained a tree). So the answer for this component will be 2^{X-1}. We can multiply the answers for each components to get our final answer.
TIME COMPLEXITY
O(N+Q) for every test case
SOLUTIONS
Setter's 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 pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define debug(x) cerr << #x << " = " << x << endl
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
int rnd (int l, int r) {
return uniform_int_distribution<int> (l, r)(gen);
}
const int N = 1e6+5;
const int mod = 998244353;
int n, q;
vector <int > g[N];
int used[N];
int comp_size;
int mult(int a, int b) {
return a * (ll) b % mod;
}
int bpow(int a, int b) {
int res = 1;
while(b > 0) {
if(b & 1) res = mult(res, a);
a = mult(a, a);
b >>= 1;
}
return res;
}
void dfs(int v) {
if(used[v])
return;
used[v] = 1;
++comp_size;
// visiting new node
for (auto to : g[v]) {
dfs(to);
}
}
void solve() {
cin >> n >> q;
for (int i = 1; i <= q; ++i) {
int l, r;
cin >> l >> r;
g[--l].pb(r);
g[r].pb(l);
}
int ans = 1;
for (int i = 0; i <= n; ++i) {
if(used[i])
continue;
comp_size = 0;
dfs(i);
ans = mult(ans, bpow(2, comp_size - 1));
}
cout << ans << '\n';
}
int32_t main () {
SpeedForce;
int TestCases = 1;
//cin >> TestCases;
for (int TestCase = 1; TestCase <= TestCases; ++TestCase) {
//cout << "Case #" << TestCase << ": ";
solve();
}
return 0;
}
// B...a
Tester's Solution 1
#include <bits/stdc++.h>
using namespace std;
struct dsu {
public:
dsu() : _n(0) {}
dsu(int n) : _n(n), parent_or_size(n, -1) {}
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
std::vector<int> parent_or_size;
};
int main() {
int n, q;
cin >> n >> q;
dsu d(n + 1);
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
d.merge(l - 1, r);
}
const long long mod = 998244353;
vector<long long> fact(n + 2), inv(n + 2), inv_fact(n + 2);
fact[0] = inv[0] = inv_fact[0] = 1;
fact[1] = inv[1] = inv_fact[1] = 1;
for (int i = 2; i < n + 2; i++) {
fact[i] = fact[i - 1] * i % mod;
inv[i] = (mod - inv[mod % i] * (mod / i) % mod) % mod;
inv_fact[i] = inv_fact[i - 1] * inv[i] % mod;
}
auto C = [&](int i, int j) {
return fact[i] * inv_fact[j] % mod * inv_fact[i - j] % mod;
};
long long ans = 1;
for (int i = 0; i < n + 1; i++) {
if (d.leader(i) == i) {
int sz = d.size(i);
long long ways = 0;
for (int j = 0; j <= sz; j += 2) {
ways += C(sz, j);
ways %= mod;
}
ans *= ways;
ans %= mod;
}
}
cout << ans << endl;
return 0;
}
Tester's Solution 2
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
/**
* Disjoint Set
* Source: Adapted from Aeren and Atcoder Library
* Description: Data structure to keep a collection of disjoint sets which contain the elements {0, 1, ..., n-1}
* Implements both path compression and union by size
* Methods:
* (1) int get_root(int u): Find a representative of the set containing u
* (2) int size(int u): Returns the size of the set containing u
* (3) bool same_set(int u, int v): Check whether u and v are in the same set
* (4) bool merge(int u, int v): Merge the sets containing u and v if they are different, returns success of merge
* (5) vector group_up(): Returns the collection of disjoint sets as a vector of vectors
*
* Time: Amortized O(n alpha(n)) for n operations
* Space: O(n)
* Tested on Codeforces EDU
*/
struct DSU {
private:
std::vector<int> parent_or_size;
public:
DSU(int n = 1): parent_or_size(n, -1) {}
int get_root(int u) {
if (parent_or_size[u] < 0) return u;
return parent_or_size[u] = get_root(parent_or_size[u]);
}
int size(int u) { return -parent_or_size[get_root(u)]; }
bool same_set(int u, int v) {return get_root(u) == get_root(v); }
bool merge(int u, int v) {
u = get_root(u), v = get_root(v);
if (u == v) return false;
if (parent_or_size[u] > parent_or_size[v]) std::swap(u, v);
parent_or_size[u] += parent_or_size[v];
parent_or_size[v] = u;
return true;
}
std::vector<std::vector<int>> group_up() {
int n = parent_or_size.size();
std::vector<std::vector<int>> groups(n);
for (int i = 0; i < n; ++i) {
groups[get_root(i)].push_back(i);
}
groups.erase(std::remove_if(groups.begin(), groups.end(), [&](auto &s) { return s.empty(); }), groups.end());
return groups;
}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int n, q; cin >> n >> q;
DSU D(n+1);
int comps = n+1;
for (int i = 0; i < q; ++i) {
int L, R; cin >> L >> R;
comps -= D.merge(--L, R);
}
int ans = 1, mod = 998244353;
comps = n+1-comps;
for (int i = 0; i < comps; ++i) {
ans *= 2;
ans %= mod;
}
cout << ans;
}
Editorialist's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 998244353
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=1000023;
bool vis[N];
vector <int> adj[N];
int cnt=0;
void dfs(int curr)
{
vis[curr]=1;
cnt++;
for(auto it:adj[curr])
{
if(vis[it])
continue;
dfs(it);
}
}
void solve()
{
int n,q;
cin>>n>>q;
ll ans=1;
while(q--)
{
int l,r;
cin>>l>>r;
adj[l-1].pb(r);
adj[r].pb(l-1);
}
for(int i=0;i<=n;i++)
{
if(vis[i])
continue;
cnt=0;
dfs(i);
ans*=power(2,cnt-1);
ans%=mod;
}
cout<<ans<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
int T=1;
//cin>>T;
while(T--)
solve();
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Feel free to share your approach. Suggestions are welcomed as always. 