MDSWIN2 - Editorial

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:

  1. Add an element 0\le x \le N in constant time (if the element already exists, nothing happens).
  2. Remove an element 0\le x \le N in constant time.
  3. 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 :slight_smile:

15 Likes

I was very near to think uptil here but wasn’t able to implement the right way :frowning:
Thanks @tmwilliamlin. You are great :slight_smile:

7 Likes

My solution is almost the same, but it doesn’t need to maintain the distinct counts set. I precalculated the prefix frequency arrays for all elements that occur in > \sqrt{N} times, in \mathcal{O}(N \sqrt N) time and memory, and maintain the count of counts array for the other elements in range of each query. For each query, traverse through the counts array and the prefix frequency arrays, in \mathcal{O}(\sqrt N) each.

2 Likes

very nice explanation @tmwilliamlin

1 Like

I do not get it how we maintain frequency of frequencies using mo. Maybe it is a misunderstanding of how mo works, since I do not see how to sort the query intervals in a usefull manner anyway.

Somebody explain?

The update function stores all the magic. I guess :slight_smile:

@tmwilliamlin is making the value small the most important part?, since I tried moving mo pointers and using map for original values it caused TLE even when I didn’t solve it completely. I only moved the pointers i.e 4 while loops for query as in CodeChef: Practical coding for everyone. Its a very small solution since I removed rest of the computation part just to check if mo will work or not. But when I submitted this it gave me Time Limit Exceeded already and therefore I didn’t find any point in proceeding further.

Thanks in Advance :slight_smile:

map has an extra O(logn) (even unordered_map has a big constant) so being able to use an array is definitely better

3 Likes

Okay so here’s the thing. The test cases are weak (correct me if i am missing anything).
I tried maintaining unordered_map to store count of frequencies of frequency (fof) of distinct elements. It was straining each query so got TLE. I, then opted for 2 arrays with hope that count of fof of distinct element is small enough. My add() and remove() were O(1) and only time needed was for iterating over fof. The count of fof never exceed than 5800 to be concise. Even after iterating over 1e4 for each query my solution got passed. Did i really not deserve my stars or am i missing something?
solution 1 : https://www.codechef.com/viewsolution/30444059
solution 2 : https://www.codechef.com/viewsolution/30444871

I heard that new test cases were added after the contest, you might want to submit it again?

Edit: If you mean that you iterate over the distinct counts, then it should pass.

1 Like

\sout{ this was intended. It can be proven that number of elements in fof will be at most sqrt(n). Let me know if you need proof :p Though you are iterating nearly 3*sqrt(n) values Which is a constant factor.}
Edit : It should get RTE. But test cases do no include such cases.

2 Likes

@tmwilliamlin Got AC again. @l_returns But what if we have an array of all elements equal.
Then value of fof as per my solution should have exceeded array limit and verdict as RE.
EDIT1 : AHHH Gotcha. Nvm. :smile:
EDIT2: This solution made me to push the array further. As there was only one task which was invading the array space.

1 Like

can we use Trie in somehow ?

HOW?
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.
can anyone explain me with an example?? so it becomes more clear ,please

I can’t understand why my code is WA. Can someone please tell.
https://www.codechef.com/viewsolution/30524542

The proof is not intuitive at all. I suggest you to read this in order to learn about game theory.
https://cp-algorithms.com/game_theory/sprague-grundy-nim.html

very nice explanation.

Can someone please explain that when I submit solution with MOD initialised as long long / int
it gives TLE but when I initialise MOD as ‘const int’ it gives AC .
Why this happens on a slight change as this error would have been difficult to catch in a contest ?
link using long long : CodeChef: Practical coding for everyone
using const int :CodeChef: Practical coding for everyone

Compilers work faster with operations with constant, division by constants is internally faster

this TLE is because of your ncr function as u have to find ncr in o(1) . as u have to precompute inversed_factorial also for every possible ‘i’.