CF1327F AND Segments

tony102

2021 年 09 月 07 日

2194 次浏览

暂无评论

945字数

题解

[Link](https://www.luogu.com.cn/problem/CF1327F)

## Sol

首先看到这种位运算的题目，就先看看它给的二进制操作是否独立（一般都会独立），独立的话就可以拆位做了。显然，这道题的操作只有 $\mathrm{AND}$ 操作，可以拆位。

考虑区间 $[l,r]$ 内的数的第 $k$ 位，假如限制给的 $a_i$ 在这一位上要求是 $1$ ，那么这个区间内所有的数这一位上都必须是 $1$，不用考虑贡献。

加入要求是 $0$ ，则这一段至少有一个 $0$。这一部分就是我们要计算的。考虑我们对每一位算出一个 $pos_i$ ，表示第 $i$ 位不放 $0$ 的情况下最早放 $0$ 的位置。设 $f_{i,j}$ 表示前 $i$ 位最后一个 $0$ 放在 $j$ 的位置上的方案数。

若 $j \in [pos_i, i)$ ，那么方案数不变直接从上一位继承过来。$f_{i,j} = f_{i-1,j}$

若 $j = i$ ，则前面 $[pos_{i-1}, i - 1]$ 的 $f$ 都可以贡献到 $f_{i,j}$ 上，即 $f_{i,j} = \sum\limits_{j = pos_{i-1}}^{i-1} f_{i-1,j}$

可以发现 $pos_i$ 单调不降，每次把 $f_{i,j}$ 加进来的时候把前面要出去的 $f$ 刷成 $0$ 即可。

## Code

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

typedef long long LL;
const int SIZE = 5e5 + 5;
const LL mod = 998244353;

int n, K, m;
int ql[SIZE], qr[SIZE], bit[SIZE], dif[SIZE], pos[SIZE];
LL f[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

int main() {
	LL ans = 1ll;
	n = read(), K = read(), m = read();
	for (int i = 1; i <= m; ++ i) ql[i] = read(), qr[i] = read() + 1, bit[i] = read();
	for (int k = 0; k < K; ++ k) {
		for (int i = 0; i <= n + 1; ++ i) f[i] = 0ll, dif[i] = pos[i] = 0;
		for (int i = 1; i <= m; ++ i) {
			if ((1 << k) & bit[i]) ++ dif[ql[i]], -- dif[qr[i]];
			else pos[qr[i]] = std::max(pos[qr[i]], ql[i]);
		}
		for (int i = 2; i <= n + 1; ++ i) dif[i] += dif[i - 1], pos[i] = std::max(pos[i], pos[i - 1]);
		LL sum = 1; int j = 0; f[0] = 1ll;
		for (int i = 1; i <= n + 1; ++ i) {
			for ( ; j < pos[i]; ++ j) sum = (sum - f[j] + mod) % mod, f[j] = 0ll;
			f[i] = dif[i] ? 0ll : sum, sum = (sum + f[i]) % mod;
		}
		ans = ans * f[n + 1] % mod;
	}
	printf("%lld\n", ans % mod);
 	return 0;
}
```

最后修改：2021 年 09 月 07 日