题解 CF1097F 【Alex and a TV Show】

Nemlit

2019-10-06 10:14:24

Solution

妙妙题…… 这道题这要求%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; } ```