Home » 国际竞赛 » Details

USACO 2020 December Contest, Platinum Problem 3. Cowmistry

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日下午3:15

USACO 2020 December Contest, Platinum Problem 3. Cowmistry

Bessie has been procrastinating on her cow-mistry homework and now needs your help! She needs to create a mixture of three different cow-michals. As all good cows know though, some cow-michals cannot be mixed with each other or else they will cause an explosion. In particular, two cow-michals with labels $a$ and $b$ can only be present in the same mixture if $a \oplus b \leq K$ ( $1 \leq K \leq 10^{9}$ ).

NOTE: Here, $a \oplus b$ denotes the "bitwise exclusive or'' of non-negative integers $a$ and $b$ . This operation is equivalent to adding each corresponding pair of bits in base 2 and discarding the carry. For example,

0 \oplus 0 = 1 \oplus 1 = 0,

1 \oplus 0 = 0 \oplus 1 = 1,

5 \oplus 7 = 1012 \oplus 1112 = 0102 = 2.

Bessie has $N$ ( $1 \leq N \leq 2 \cdot 10^{4}$ ) boxes of cow-michals and the $i$ -th box contains cow-michals labeled $l_{i}$ through $r_{i}$ inclusive $(0 \leq l_{i} \leq r_{i} \leq 10^{9})$ . No two boxes have any cow-michals in common. She wants to know how many unique mixtures of three different cow-michals she can create. Two mixtures are considered different if there is at least one cow-michal present in one but not the other. Since the answer may be very large, report it modulo $10^{9} + 7$ .

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains two integers $N$ and $K$ .Each of the next $N$ lines contains two space-separated integers $l_{i}$ and $r_{i}$ . It is guaranteed that the boxes of cow-michals are provided in increasing order of their contents; namely, $r_{i} < l_{i + 1}$ for each $1 \leq i < N$ .

OUTPUT FORMAT (print output to the terminal / stdout):

The number of mixtures of three different cow-michals Bessie can create, modulo $10^{9} + 7$ .

SAMPLE INPUT:

1 13
0 199

SAMPLE OUTPUT:

We can split the chemicals into 13 groups that cannot cross-mix: $(0 \dots 15)$ , $(16 \dots 31)$ , $\dots$ $(192 \dots 199)$ . Each of the first twelve groups contributes $352$ unique mixtures and the last contributes $56$ (since all $(\binom{8}{3})$ combinations of three different cow-michals from $(192 \dots 199)$ are okay), for a total of $352 \cdot 12 + 56 = 4280$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

SCORING

Test cases 3-4 satisfy $max (K, r_{N}) \leq 10^{4}$ .
Test cases 5-6 satisfy $K = 2^{k} - 1$ for some integer $k \geq 1$ .
Test cases 7-11 satisfy $max (K, r_{N}) \leq 10^{6}$ .
Test cases 12-16 satisfy $N \leq 20$ .
Test cases 17-21 satisfy no additional constraints.

Problem credits: Benjamin Qi

USACO 2020 December Contest, Platinum Problem 3. Cowmistry 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(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 $\leq$ to $<$ . Then define $P$ to be the smallest power of two greater than $K$ . Every triangle must satisfy

⌊ x P ⌋ = ⌊ y P ⌋ = ⌊ z P ⌋ .

Case 1: $⌊ \frac{x}{P / 2} ⌋ = ⌊ \frac{y}{P / 2} ⌋ = ⌊ \frac{z}{P / 2} ⌋$

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 $⌊ \frac{x}{P / 2} ⌋ = ⌊ \frac{y}{P / 2} ⌋ = ⌊ \frac{z}{P / 2} ⌋$ is not satisfied. WLOG assume that $⌊ \frac{x}{P / 2} ⌋ < ⌊ \frac{y}{P / 2} ⌋ = ⌊ \frac{z}{P / 2} ⌋$ . 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 \geq 0$ and each $x \in [P t, P t + P / 2)$ , we must add $(\binom{{y : y \in [P t + P / 2, P t + P) and x \oplus y < K}}{2})$ to the answer. This is what the recursive function $add_to_answer$ in my code below accounts for (read it for more details).

The number of times $add_to_answer$ is called and the overall running time are $O (N \log_{2} K)$ . $O (N \cdot (\log_{2} K)^{2})$ or $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; }
	friend string to_string(mint a) { return to_string(a.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);
	};
	for (auto& t: a) ad(A[0],t), ad(A[1],{t.first-block/2,t.second-block/2});
	for (auto& t: b) ad(B[0],t), ad(B[1],{t.first-block/2,t.second-block/2});
	if (K&(block/2)) {
		for(int i=0; i<2; ++i) add_to_answer(A[i],B[i^1],block/2,cur+total_length(B[i]));
	} else {
		for(int i=0; i<2; ++i) add_to_answer(A[i],B[i],block/2,cur);
	}
}

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
		add_to_answer(tot[i],tot[i^1],P2,0); // case 2
	}
}

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).

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