T461430 「Daily OI Round 4」Mine

T461430 「Daily OI Round 4」Mine

解题思路

首先，有个简单的想法就是我们考虑选择的那个采矿点是谁，但是我们发现，如果直接算，会重复，比如采矿点 \(A\) 和 采矿点 \(B\) 所能采集的线段集合如果有交，显然会方案数会重复。

这里学到一个计数的技巧：

考虑人为钦定一些顺序或者限制，我们观察对于任意一种选择线段的方案，由于选择的线段非空，我们把所选的线段按左端点排序，那么我们考虑第一个线段，其第一个碰到的采矿点，我们以这个为标识，我们钦定这个线段被这个采矿点所唯一监管。

那么任意一组方案，必然会被这样钦定的唯一采矿点所监管，这样我们就把答案拆成了若干个采矿点的贡献之和，这样一定是不重不漏的，因为任意一组方案按上面的方法钦定划分，必然只会被唯一一个采矿点监管。

故我们只要计算，被某个采矿点监管的方案即可，然后累加。

我们设被 \(i\) 这个采矿点所监管的线段（每个线段第一个碰到的采矿点）的数量为 \(b_i\)，然后经过 \(i\) 这个采矿点的线段数量为 \(c_i\)，我们可以得到这个点的贡献为：\((2^{b_i}-1)\times 2^{c_i-b_i}\)。

我们可以这样理解，我们要计算每个点的贡献，则必须要选择一条被其监管的线段，然后其余线段可选可不选。

故最后答案为：\(\sum_{i=1}^m(2^{b_i}-1)\times 2^{c_i-b_i}\)。

Code

#include <bits/stdc++.h>

typedef long long LL;

const int N = 1e5 + 10, mod = 998244353;
int l[N], r[N], a[N], b[N], c[N];

LL ksm(LL a, LL b) {
	LL res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n, m;
	std::cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		std::cin >> l[i] >> r[i];
	}

	for (int i = 1; i <= m; i++) {
		std::cin >> a[i];
	}

	std::sort(a + 1, a + 1 + m);

	for (int i = 1; i <= n; i++) {
		l[i] = std::lower_bound(a + 1, a + 1 + m, l[i]) - a;
		r[i] = std::upper_bound(a + 1, a + 1 + m, r[i]) - a;
		c[l[i]]++, c[r[i]]--;
		if (l[i] < r[i]) {
			b[l[i]]++;
		}
	}

	for (int i = 1; i <= m; i++) {
		c[i] += c[i - 1];
	}

	LL ans = 0;

	for (int i = 1; i <= m; i++) {
		ans += (ksm(2, b[i]) - 1) * ksm(2, c[i] - b[i]) % mod;
		ans %= mod;
	}

	if (ans < 0) ans += mod;

	std::cout << ans << '\n';

	return 0;
}