题解 CF1097F 【Alex and a TV Show】

妙妙题……

这道题这要求%2的个数，肯定有什么性质

于是我们想到了用\(bitset\)来处理

由于三操作有\(gcd\)，于是我们又想到用反演来解决

我们回忆一下反演的柿子

设\(f(x)\)为x出现了多少次，\(F(x)\)为x的倍数出现了多少次

\[F(d) = \sum_{d|x}f(x)
\]

跟据反演，我们有：

\[f(x) = \sum_{x |d}F(d) * \mu(\frac{d}{x})
\]

我们要求的数即为\(f(v)\)

由于\(\mu\)的取值只有\(-1, 0, 1\)，在膜二意义下只有\(0, 1\)

我们用\(a[x][y]\)表示\(x\)集合内的y即y的倍数出现了多少次（\(F(y)\)），再用\(u[x][y]\)表示\(\mu(\frac{y}{x})\)，我们要求的\(f(v) = a[x]\&u[v]\)

再来重新考虑所有操作：

对于1操作，预处理出每一个v的所有约数的\(bitset\)，赋值即可

对于2操作，直接用\(a[x]=a[y]^a[z]\)即可

对于3操作，\(a[x] = a[y]\&a[z]\)

对于4操作，用上述方法求出\(bitset\)后的\(1\)的数量

\(Code:\)

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define re register

il int read() {

    re int x = 0, f = 1; re char c = getchar();

    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();

    return x * f;

}

#define rep(i, s, t) for(re int i = s; i <= t; ++ i)

#define maxn 7001

#define maxm 100005

int n, m, prim[maxn], vis[maxn], mu[maxn], cnt;

bitset<maxn>G[maxn], a[maxm], u[maxn];

int main() {

	n = read(), m = read(), mu[1] = 1;

	rep(i, 2, 7000) {

		if(!vis[i]) prim[++ cnt] = i, mu[i] = -1;

		for(re int j = 1; j <= cnt && prim[j] * i <= 7000; ++ j) {

			vis[i * prim[j]] = 1;

			if(i % prim[j] == 0) break;

			mu[i * prim[j]] = -mu[i];

		}

	}

	rep(i, 1, 7000) {

		for(re int j = i; j <= 7000; j += i) G[j][i] = 1, u[i][j] = mu[j / i] != 0;

	}

	while(m --) {

		int opt = read(), x = read();

		if(opt == 1) a[x] = G[read()];

		if(opt == 2) a[x] = a[read()] ^ a[read()];

		if(opt == 3) a[x] = a[read()] & a[read()];

		if(opt == 4) printf("%d", (u[read()] & a[x]).count() & 1);

	}

	return 0;

}

巴特西

题解 CF1097F 【Alex and a TV Show】

\(Code:\)

最新文章

热门文章