PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Md Sabbir Rahman
Tester: Suchan Park
Editorialist: William Lin
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Nim, Mo’s algorithm, Basic Combinatorics
PROBLEM:
You are given an array A. You are given Q independent queries (L, R). For each query, a two-player game will be played on the array A[L, R]. The two players will alternate, with the first player starting. On each turn, a player has to remove a non-empty subset of elements from the array with the same value. The player who can’t choose any elements loses. Find the number of subsets the first player can choose to win.
QUICK EXPLANATION:
This is a Nim game, where each distinct element in the array corresponds to a pile and the size of the pile is the number of occurrences of that element. Using Mo’s algorithm, we can maintain the counts of elements in the subarrays for the queries. Let x be the xor of all counts. There are O(\sqrt N) distinct counts, so for each query, we can iterate through all distinct counts c. We check if c \oplus x < c, and if so, we add c \choose {c\oplus x} to the answer.
EXPLANATION:
We should remap the values in A to values between 1 and N so that we can store counts of values in an array of size N.
Note that the game is really just a Nim game.
Explanation
- Both players alternate.
- The player who can’t move loses.
- Each turn the player must remove at least one element.
- Each turn the player can only remove from one pile → Each turn the player can only remove one type of element.
A state is losing if the xor sum of all pile sizes is 0 (standard Nim fact). In our case, the each pile is the set of elements with the same value and the pile sizes are the counts of a certain element.
The first thing we need to do is to calculate the counts of values in the subarray. Let c_i be the number of times i appears in the subarray and let x be the xor sum of c_i for all valid i.
In order for the first player to win, they need to modify one of the pile sizes so that x becomes 0 (giving the second player a losing state).
Let’s iterate over i and count the number of ways the first player can remove elements with value i to make x=0. Let d be the new count of value i after we remove some elements. x \oplus c_i \oplus d is the new xor sum of the pile sizes, and we need that to be 0. We can find d to be x \oplus c_i.
Since we are removing elements from the pile, we need d<c_i to be satisfied, otherwise the number of ways to remove i and win is 0. How many ways are there if d<c_i? We are choosing d of the elements to keep (and removing the rest), so we should add c_i \choose d to the answer.
In summary, a solution which gets the first two subtasks (30 points) is below:
- For each query:
- Find all c_i and calculate x.
- Iterate through all valid values i in A[L, R]:
- If (c_i \oplus x) < c_i, add c_i \choose {c_i\oplus x} to the answer.
The full solution is similar, but we need some tricks to speed up the current solution. The first obstacle is calculating c_i and x fast enough and the second obstacle is iterating through all i and calculating the answer fast enough.
Answering subarray queries related to the counts of values in the subarray is a standard Mo’s Algorithm problem. We can process the queries in an order so that when we answer a query, the array c will be updated to represent the counts for the subarray. Maintaing x in this algorithm is not much harder.
Details
While performing Mo’s algorithm, when we need to add an element at index i to the subarray, we call upd(i, 1). When we need to remove an element at index i from the subarray, we call upd(i, -1).
upd(i, y):
x^=c[i]
c[i]+=y
x^=c[i]
How do we overcome the second obstacle? Notice that if two piles have the same size, then their answer will be the same. Let cc_i be the number of j such that c_j=i (count array of the count array c). While finding the answer, we will only iterate through distinct counts j and multiply the answer for the count by cc_j.
Notice that the sum of all counts \le N, so the number of distinct counts is O(\sqrt N) (sum of first O(\sqrt N) positive integers is O(N)). If we can somehow maintain cc and the set of distinct counts for each query, we can answer each query in O(\sqrt N).
cc is pretty simple to maintain in Mo’s algorithm. We can maintain the set of distinct counts with a binary search tree (set in C++), but it adds an additional O(\log N) factor which will cause our solution to TLE.
Instead, we will use a data structure which supports:
- Add an element 0\le x \le N in constant time (if the element already exists, nothing happens).
- Remove an element 0\le x \le N in constant time.
- Iterate over all elements in the set in O(s) time if s is the number of elements in the set.
The setter, tester, and I each have different solutions for this data structure.
Setter
Maintain a doubly linked list with the counts as the elements. This only works in this problem because the counts either increase or decrease by 1.
Tester
Create a bitset of size N+1. Adding and removing elements correspond to setting and clearing bits (which are constant time). Iterating over the set bits in a bitset works in O(s+N/64), which is good enough.
Editorialist
The first and third operations can be supported easily with a list (vector in C++). We will additionally store a boolean array inlist[i] which tells us if an element is in the list. When we add an element i to the set, we should check that inlist[i] is false first.
When we want to perform the second operation, we will do so “lazily”: we won’t actually do it, but the next time we iterate over the elements in the set, we will remove it if we find the it should have been removed (if cc=0).
The pseudocode for the third operation is shown below:
newlist
for x in list:
if x should have been removed
inlist[x]=false
continue
//do whatever with x
add x to newlist
list = newlist
Here is the final upd function when we add or remove elements in Mo’s algorithm:
upd(i, y):
x^=c[i]
--cc[c[i]]
if cc[c[i]]==0:
remove c[i] from the set of distinct counts
c[i]+=y
x^=c[i]
++cc[c[i]]
add c[i] to the set of distinct counts (if it is not already in the set)
Mo’s algorithm runs in O(N\sqrt Q) and each query takes O(\sqrt N) time, so the final time complexity is O(N\sqrt Q + Q \sqrt N).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
ll mod = 998244353;
const ld error = 1e-8;
const ld PI = acosl(-1); //const ld PI = acosl(-1)
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define eq(x, y) (fabs((x)-(y))<error)
#define bt(i) (1LL<<(i))
#define debug(x) cerr<<#x<<" = "<<(x)<<"\n"
#define hoise cerr<<"hoise - "<<__LINE__<<"\n"
#define tham getchar()
mt19937 rng((unsigned)chrono::system_clock::now().time_since_epoch().count()); //mt199937_64 for ll
inline ll MOD(ll x, ll m = mod)
{
ll y = x % m;
return (y >= 0) ? y: y+m;
}
const int inf = 1e9;
const ll infl = 1e18+1;
const int nmax = bt(17);
///=========================================== template =======================================================
ll modexpo(ll x, ll n, ll m = mod){
ll ret = 1%m;
while(n){
if(n&1) ret = ret * x % m;
x = x * x % m;
n >>= 1;
}
return ret;
}
ll fac[nmax];
ll facinv[nmax];
void precal()
{
fac[0] = 1;
for(int i = 1; i<nmax; i++)
fac[i] = (fac[i-1]*i) % mod;
facinv[nmax-1] = modexpo(fac[nmax-1], mod-2);
for(int i = nmax-1; i>0; i--)
facinv[i-1] = (facinv[i]*i) % mod;
return;
}
ll NCR(int n, int r){
if(n < r) return 0;
return fac[n] * facinv[r] % mod * facinv[n-r] % mod;
}
int arr[nmax], bsz = 1;
ll ans[nmax];
struct query{
int l, r, i;
bool operator<(query other){
return make_pair(l/bsz, r) < make_pair(other.l/bsz, other.r);
}
} Q[nmax];
int freq[nmax], frfreq[nmax], xorval;
int L[nmax], R[nmax];
/*
inserting frequency a (if needed)
*/
void ins(int a, int b, int c){
if(frfreq[b] != 1) return;
L[b] = a, R[b] = c;
R[a] = L[c] = b;
}
/*
deleting frequency a (if needed)
*/
void del(int a){
if(frfreq[a] != 0) return;
R[L[a]] = R[a];
L[R[a]] = L[a];
}
/*
Adding or removing value x from current active subarray
*/
void update(int x, int c){
freq[x] += c;
frfreq[freq[x]-c]--;
frfreq[freq[x]]++;
xorval ^= freq[x] ^ (freq[x] - c);
if(c == 1) ins(freq[x]-1 , freq[x], R[freq[x]-1]);
else ins(L[freq[x]+1], freq[x], freq[x]+1);
del(freq[x]-c);
return;
}
/*
Initialization before Mo's algo
*/
void init(int n){
memset(freq, 0, sizeof(freq));
memset(frfreq, 0, sizeof(freq));
frfreq[0] = n+1;
xorval = 0;
L[0] = L[nmax-1] = 0;
R[0] = R[nmax-1] = nmax-1;
return;
}
/*
Mo's algo to maintain frequency of each element and frequency of these frequencys.
*/
void mo(int n, int m){
bsz = max(int(n / sqrt(m+1)), 1);
sort(Q, Q+m);
init(n);
int l = 0, r = 0;
update(arr[0], 1);
for(int i = 0; i<m; i++){
query q = Q[i];
while(r < q.r) update(arr[++r], 1);
while(q.l < l) update(arr[--l], 1);
while(q.r < r) update(arr[r--], -1);
while(l < q.l) update(arr[l++], -1);
ans[q.i] = 0;
for(int cur = 0; cur != nmax-1; cur = R[cur]){
if((cur^xorval) < cur){
ans[q.i] += frfreq[cur]*NCR(cur, cur^xorval);
if(ans[q.i] >= mod) ans[q.i] %= mod;
}
}
}
return;
}
int main(){
FASTIO;
precal();
int tc;
cin>>tc;
assert(1 <= tc && tc <= 5);
for(int cs = 1; cs <=tc; cs++){
int n, cnt = 0;
cin>>n;
assert(1 <= n && n <= 1e5);
map<int, int> mp;
for(int i = 0; i<n; i++){
cin>>arr[i];
assert(1 <= arr[i] && arr[i] <= 1e9);
if(!mp[arr[i]]) mp[arr[i]] = ++cnt;
arr[i] = mp[arr[i]];
}
int m;
cin>>m;
assert(1 <= m && m <= 1e5);
for(int i = 0; i<m; i++){
int l, r;
cin>>l>>r;
assert(1 <= l && l <= r && r <= n);
Q[i] = {l-1, r-1, i};
}
mo(n, m);
for(int i = 0; i<m; i++)
cout<<ans[i]<<"\n";
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
const int BUFFER_SIZE = int(1.1e5);
char _buf[BUFFER_SIZE + 10];
int _buf_pos, _buf_len;
char seekChar() {
if(_buf_pos >= _buf_len) {
_buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
_buf_pos = 0;
}
assert(_buf_pos < _buf_len);
return _buf[_buf_pos];
}
bool seekEof() {
if(_buf_pos >= _buf_len) {
_buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
_buf_pos = 0;
}
return _buf_pos >= _buf_len;
}
char readChar() {
char ret = seekChar();
_buf_pos++;
return ret;
}
int readInt(int lb, int rb) {
char c = readChar();
int mul = 1;
if(c == '-') {
c = readChar();
mul = -1;
}
assert(isdigit(c));
long long ret = c - '0';
int len = 0;
while(!seekEof() && isdigit(seekChar()) && ++len <= 19) {
ret = ret * 10 + readChar() - '0';
}
ret *= mul;
assert(len <= 18);
assert(lb <= ret && ret <= rb);
return (int)ret;
}
void readEoln() {
char c = readChar();
//assert(c == '\n');
assert(c == '\n' || (c == '\r' && readChar() == '\n'));
}
void readSpace() {
assert(readChar() == ' ');
}
// https://github.com/the-tourist/algo/blob/master/numeric/mint.cpp
template <typename T>
T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a; swap(a, m);
u -= t * v; swap(u, v);
}
assert(m == 1);
return u;
}
template <typename T>
class Modular {
public:
using Type = typename std::decay<decltype(T::value)>::type;
constexpr Modular() : value() {}
template <typename U>
Modular(const U& x) {
value = normalize(x);
}
template <typename U>
static Type normalize(const U& x) {
Type v;
if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
else v = static_cast<Type>(x % mod());
if (v < 0) v += mod();
return v;
}
const Type& operator()() const { return value; }
template <typename U>
explicit operator U() const { return static_cast<U>(value); }
constexpr static Type mod() { return T::value; }
Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
Modular& operator++() { return *this += 1; }
Modular& operator--() { return *this -= 1; }
Modular operator++(int) { Modular result(*this); *this += 1; return result; }
Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
Modular operator-() const { return Modular(-value); }
template <typename U = T>
typename std::enable_if<std::is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
#ifdef _WIN32
uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
asm(
"divl %4; \n\t"
: "=a" (d), "=d" (m)
: "d" (xh), "a" (xl), "r" (mod())
);
value = m;
#else
value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
return *this;
}
template <typename U = T>
typename std::enable_if<std::is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) {
int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
value = normalize(value * rhs.value - q * mod());
return *this;
}
template <typename U = T>
typename std::enable_if<!std::is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
value = normalize(value * rhs.value);
return *this;
}
Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
template <typename U>
friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
template <typename U>
friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
template <typename U>
friend std::istream& operator>>(std::istream& stream, Modular<U>& number);
private:
Type value;
};
template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }
template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }
template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
assert(b >= 0);
Modular<T> x = a, res = 1;
U p = b;
while (p > 0) {
if (p & 1) res *= x;
x *= x;
p >>= 1;
}
return res;
}
template <typename T>
std::string to_string(const Modular<T>& number) {
return to_string(number());
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
return stream << number();
}
template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
typename std::common_type<typename Modular<T>::Type, int64_t>::type x;
stream >> x;
number.value = Modular<T>::normalize(x);
return stream;
}
/*
using ModType = int;
struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;
*/
constexpr int MOD = 998244353;
using Mint = Modular<std::integral_constant<std::decay<decltype(MOD)>::type, MOD>>;
const int MAXN = int(1e5);
Mint fac[MAXN+5], inv[MAXN+5], invfac[MAXN+5];
Mint comb (int n, int r) {
return fac[n] * invfac[r] * invfac[n-r];
}
inline int64_t gilbertOrder(int x, int y, int pow, int rotate) {
if (pow == 0) {
return 0;
}
int hpow = 1 << (pow-1);
int seg = (x < hpow) ? (
(y < hpow) ? 0 : 3
) : (
(y < hpow) ? 1 : 2
);
seg = (seg + rotate) & 3;
const int rotateDelta[4] = {3, 0, 0, 1};
int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
int nrot = (rotate + rotateDelta[seg]) & 3;
int64_t subSquareSize = int64_t(1) << (2*pow - 2);
int64_t ans = seg * subSquareSize;
int64_t add = gilbertOrder(nx, ny, pow-1, nrot);
ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
return ans;
}
struct Query {
int l, r, q;
int64_t ord;
Query(int x,int y,int i){
l=x; r=y; q=i;
ord = gilbertOrder(l, r, 17, 0);
}
};
namespace Solver {
int all_xored;
int freq[int(1.1e5)];
int cnt[int(1.1e5)];
std::bitset<100005> alive;
void clear() {
all_xored = 0;
for(int i = 0; i < 100001; i++) alive[i] = false;
memset(freq, 0, sizeof freq);
memset(cnt, 0, sizeof cnt);
cnt[0] = 1.1e5;
}
void change_cnt(int f, int d) {
all_xored ^= f;
if(cnt[f] == 0) {
assert(d == +1);
alive.set(f,true);
}
cnt[f] += d;
if(cnt[f] == 0) {
assert(d == -1);
alive.set(f, false);
}
}
void remove(int x) {
change_cnt(freq[x], -1);
freq[x] -= 1;
change_cnt(freq[x], +1);
}
void add(int x) {
change_cnt(freq[x], -1);
freq[x] += 1;
change_cnt(freq[x], +1);
}
Mint getValue() {
if(all_xored == 0) {
return 0;
}
Mint ans;
for(int f = alive._Find_first(); f < 100001; f = alive._Find_next(f)) {
int c = cnt[f];
int v = all_xored ^ f;
if(f >= v) ans += c * comb(f, v);
}
return ans;
}
};
void run() {
int N = readInt(1, MAXN);
readEoln();
std::vector<int> A(N);
std::vector<std::vector<int>::iterator> idxes;
for(int i = 0; i < N; i++) {
A[i] = readInt(1, int(1e9));
if(i + 1 < N) readSpace(); else readEoln();
idxes.push_back(A.begin() + i);
}
std::sort(idxes.begin(), idxes.end(), [&](const std::vector<int>::iterator &it1, const std::vector<int>::iterator &it2) {
return *it1 < *it2;
});
for(int i = 0, c = 1; i < N; c++) {
int j = i;
int v = *idxes[i];
while(j < N && *idxes[j] == v) *idxes[j++] = c;
i = j;
}
int Q = readInt(1, 100000);
readEoln();
std::vector<Query> queries;
for(int q = 0; q < Q; q++) {
int l = readInt(1, N);
readSpace();
int r = readInt(l, N);
readEoln();
l -= 1;
r -= 1;
queries.emplace_back(l, r, q);
/*
std::unordered_map<int, int> freq;
for(int i = l; i <= r; i++) {
freq[A[i]] += 1;
}
int all_xored = 0;
for(auto &it : freq) all_xored ^= it.second;
Mint ans = 0;
if(all_xored != 0) {
for(auto &it : freq) {
all_xored ^= it.second;
if(it.second >= all_xored) {
ans += comb(it.second, all_xored);
}
all_xored ^= it.second;
}
}
printf("%d\n", ans());*/
}
std::sort(queries.begin() ,queries.end(), [&](const Query &q1, const Query &q2) {
return q1.ord < q2.ord;
});
std::vector<Mint> ans(Q);
int l = queries.front().l;
int r = queries.front().l - 1;
Solver::clear();
for(Query &query : queries) {
while(l > query.l) Solver::add(A[--l]);
while(r < query.r) Solver::add(A[++r]);
while(l < query.l) Solver::remove(A[l++]);
while(r > query.r) Solver::remove(A[r--]);
ans[query.q] = Solver::getValue();
}
for(auto &it : ans) printf("%d\n", it());
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int T = readInt(1, 5);
readEoln();
fac[0] = 1;
invfac[0] = 1;
fac[1] = 1;
inv[1] = 1;
invfac[1] = 1;
for(int i = 2; i <= MAXN; i++) {
fac[i] = fac[i-1] * i;
inv[i] = inv[MOD % i] * (MOD - MOD / i);
invfac[i] = invfac[i-1] * inv[i];
assert((fac[i] * invfac[i])() == 1);
assert((i * inv[i])() == 1);
}
while(T--) {
run();
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN=1e5, B=300, M=998244353;
ll iv[mxN+1], f1[mxN+1], f2[mxN+1];
int n, q, a[mxN], ans[mxN], c[mxN], tx;
//counts of counts
int cc[mxN+1];
//the distinct counts
vector<int> d;
//status of the distinct counts
bool bd[mxN+1];
struct query {
int l, r, i;
bool operator<(const query &o) const {
//compare by block of left index first then right index
return make_pair(l/B, r)<make_pair(o.l/B, o.r);
}
} b[mxN];
//update the count of x by y
void upd(int x, int y) {
tx^=c[x];
--cc[c[x]];
c[x]+=y;
tx^=c[x];
++cc[c[x]];
if(!bd[c[x]]) {
d.push_back(c[x]);
bd[c[x]]=1;
}
}
void solve() {
//input
cin >> n;
map<int, int> mp;
for(int i=0; i<n; ++i) {
cin >> a[i];
//make the values small
if(mp.find(a[i])==mp.end())
mp.insert({a[i], mp.size()});
a[i]=mp[a[i]];
}
cin >> q;
for(int i=0; i<q; ++i) {
cin >> b[i].l >> b[i].r, --b[i].l, --b[i].r;
b[i].i=i;
}
//sort queries
sort(b, b+q);
//reset values
memset(ans, 0, 4*q);
memset(c, 0, 4*n);
tx=0;
memset(cc, 0, 4*(n+1));
d={};
memset(bd, 0, 4*(n+1));
//process queries
for(int i=0, l=0, r=-1; i<q; ++i) {
//modify range from previous range
while(b[i].l<l)
upd(a[--l], 1);
while(b[i].r>r)
upd(a[++r], 1);
while(b[i].l>l)
upd(a[l++], -1);
while(b[i].r<r)
upd(a[r--], -1);
//find answer for current range
//iterate over distinct counts
vector<int> nd;
for(int c : d) {
if(!cc[c]) {
//this count doesn't actually occur
bd[c]=0;
continue;
}
int c2=c^tx;
if(c2<c) {
//c choose c2
ans[b[i].i]=(ans[b[i].i]+cc[c]*f1[c]%M*f2[c2]%M*f2[c-c2])%M;
}
nd.push_back(c);
}
d=nd;
}
//output
for(int i=0; i<q; ++i)
cout << ans[i] << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//precalculate math
iv[1]=1;
for(int i=2; i<=mxN; ++i)
iv[i]=M-M/i*iv[M%i]%M;
f1[0]=f2[0]=1;
for(int i=1; i<=mxN; ++i) {
f1[i]=f1[i-1]*i%M;
f2[i]=f2[i-1]*iv[i]%M;
}
int t;
cin >> t;
while(t--)
solve();
}
Please give me suggestions if anything is unclear so that I can improve. Thanks 
