(Analysis by Benjamin Qi)

Note: I used the first sample case as a problem in a math competition a while ago.

First, add one to $K$ and change $\le$ to $<$. Then define $P$ to be the smallest power of two greater than $K$. Every triangle must satisfy

$$\left\lfloor \frac{x}{P}\right\rfloor=\left\lfloor \frac{y}{P}\right\rfloor=\left\lfloor \frac{z}{P}\right\rfloor.$$

Case 1: $\left\lfloor \frac{x}{P/2}\right\rfloor=\left\lfloor \frac{y}{P/2}\right\rfloor=\left\lfloor \frac{z}{P/2}\right\rfloor$

Then $x$, $y$, and $z$ definitely form a triangle. Accounting for this case alone is sufficient for test cases 5 and 6.

Case 2: $x,y,z$ form a triangle but the condition $\left\lfloor \frac{x}{P/2}\right\rfloor=\left\lfloor \frac{y}{P/2}\right\rfloor=\left\lfloor \frac{z}{P/2}\right\rfloor$ is not satisfied. WLOG assume that $\left\lfloor \frac{x}{P/2}\right\rfloor<\left\lfloor \frac{y}{P/2}\right\rfloor=\left\lfloor \frac{z}{P/2}\right\rfloor$. Clearly $y\oplus z<K$ holds, so we only need to check that both $x\oplus y<K$ and $x\oplus z<K$ hold.

So for all $t\ge 0$ and each $x\in [Pt,Pt+P/2)$, we must add $\binom{\{y:y\in [Pt+P/2,Pt+P)\text{ and }x\oplus y<K\}}{2}$ to the answer. This is what the recursive function $\texttt{add_to_answer}$ in my code below accounts for (read it for more details).

The number of times $\texttt{add_to_answer}$ is called and the overall running time are $\mathcal{O}(N\log_2K)$. $\mathcal{O}(N\cdot (\log_2 K)^2)$ or $\mathcal{O}(N\cdot (\log_2 K)^3)$ solutions with reasonable constant factors should also receive full credit.

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

const int MOD = 1e9+7; // 998244353;

template<class T> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; } // set a = min(a,b)
template<class T> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; }

/**
* Description: modular arithmetic operations
* Source:
* KACTL
* https://codeforces.com/blog/entry/63903
* https://codeforces.com/contest/1261/submission/65632855 (tourist)
* https://codeforces.com/contest/1264/submission/66344993 (ksun)
* also see https://github.com/ecnerwala/cp-book/blob/master/src/modnum.hpp (ecnerwal)
* Verification:
* https://open.kattis.com/problems/modulararithmetic
*/

template<int MOD, int RT> struct mint {
static const int mod = MOD;
int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
mint() { v = 0; }
mint(long long _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
if (v < 0) v += MOD; }
friend bool operator==(const mint& a, const mint& b) {
return a.v == b.v; }
friend bool operator!=(const mint& a, const mint& b) {
return !(a == b); }
friend bool operator<(const mint& a, const mint& b) {
return a.v < b.v; }

mint& operator+=(const mint& m) {
if ((v += m.v) >= MOD) v -= MOD;
return *this; }
mint& operator-=(const mint& m) {
if ((v -= m.v) < 0) v += MOD;
return *this; }
mint& operator*=(const mint& m) {
v = int((long long)v*m.v%MOD); return *this; }
mint& operator/=(const mint& m) { return (*this) *= inv(m); }
friend mint pow(mint a, long long p) {
mint ans = 1; assert(p >= 0);
for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans; }
friend mint inv(const mint& a) { assert(a.v != 0);
return pow(a,MOD-2); }

mint operator-() const { return mint(-v); }
mint& operator++() { return *this += 1; }
mint& operator--() { return *this -= 1; }
friend mint operator+(mint a, const mint& b) { return a += b; }
friend mint operator-(mint a, const mint& b) { return a -= b; }
friend mint operator*(mint a, const mint& b) { return a *= b; }
friend mint operator/(mint a, const mint& b) { return a /= b; }
};

vector<vector<mint<MOD,5> > > scmb; // small combinations, 5 is primitive root for both common mods
void genComb(int SZ) {
scmb.assign(SZ,vector<mint<MOD,5> > (SZ)); scmb[0][0] = 1;
for(int i=1; i<SZ; ++i) for(int j = 0; j<i+1; ++j)
scmb[i][j] = scmb[i-1][j]+(j?scmb[i-1][j-1]:0);
}

int N,K,P = 1;

mint<MOD,5> i2 = mint<MOD,5> (1)/2, i6 = mint<MOD,5> (1)/6;
mint<MOD,5> c2(mint<MOD,5> x) { return mint<MOD,5> ((long long)x.v*(x.v-1)/2); }
mint<MOD,5> c3(mint<MOD,5> x) { return x*(x-1)*(x-2)*i6; }

mint<MOD,5> ans = 0;

int total_length(const vector<pair<int,int> >& v) { // total length of intervals
int len = 0; for (auto& t: v) len += t.second-t.first+1;
return len;
}

// a and b are sets of intervals in [0,block)
// for each x in a, we want to add the following quantity to the answer:
// \binom{cur+size({y | y in b and x^y < (block-1)&K})}{2}

void add_to_answer(const vector<pair<int,int> >& a, const vector<pair<int,int> >& b, int block, mint<MOD,5> cur) {
// base cases
if (!int((a).size())) return;
if (!int((b).size())) {
ans += total_length(a)*c2(cur);
return;
}
vector<pair<int,int> > des{{0,block-1}};
if (b == des) { // b = [0,block)
cur += (block-1)&K;
ans += total_length(a)*c2(cur);
return;
}
// otherwise recurse
vector<pair<int,int> > A[2], B[2];
auto ad = [&](vector<pair<int,int> >& v, pair<int, int> p) {
ckmax(p.first,0), ckmin(p.second,block/2-1);
if (p.first > p.second) return;
v.push_back(p);
};
if (K&(block/2)) {
} else {
}
}

void deal(vector<pair<int,int> > v) { // [0,P)
int P2 = P/2;
vector<pair<int,int> > tot[2];
for (auto& t: v) {
if (t.first/P2 < t.second/P2) {
tot[0].push_back({t.first,P2-1});
tot[1].push_back({0,t.second-P2});
} else {
tot[t.first/P2].push_back({t.first%P2,t.second%P2});
}
}
for(int i=0; i<2; ++i) {
ans += c3(total_length(tot[i])); // case 1
}
}

int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N >> K;
++ K; while (P <= K) P *= 2; // P > K
K = K-P/2; assert(0 <= K && K < P/2);
mint<MOD,5> sing = P*c2(K)+2*c3(P/2); // answer for interval covering [0,P)
map<int,vector<pair<int,int> > > todo;
for(int i=0; i<N; ++i) {
int L,R; cin >> L >> R;
int LL = L/P, RR = R/P;
if (LL != RR) {
ans += (RR-LL-1)*sing;
todo[LL].push_back({L%P,P-1});
todo[RR].push_back({0,R%P});
} else {
todo[LL].push_back({L%P,R%P});
}
}
for (auto& t: todo) deal(t.second);
cout << to_string(ans) << endl;
}



A similar approach (with the same time complexity) involves writing a modified bitwise trie that supports the following operations on an array $a[\cdot]$ (where all additions come before all queries, although it is possible to support interleaved additions and queries).

• $\texttt{add}(x,y)$: For each $i\in [0,x]$ and $j\in [0,K)$, add $y$ to $a[i\oplus j]$.
• $\texttt{query}(x)$: Output $\sum_{i=0}^{x}\binom{a_i}{2}$.