Nemlit 的博客

Nemlit 的博客

By a konjac

题解 CF1097F 【Alex and a TV Show】

posted on 2019-10-06 10:14:24 | under 题解 |

妙妙题……

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