CF1097F Alex and a TV Show（莫比乌斯反演+bitset）

Description

维护 $n$ 个初始为空的可重集，支持以下操作（操作总次数为 $q$）：

1 x v : 令集合 $x$ 等于 $\left\{v\right\}$。

2 x y z : 令集合 $x$ 等于集合 $y$ 与 $z$ 的并。

3 x y z : 令集合 $x$ 等于集合 $y$ 与 $z$ 的积，$A\times B=\left\{gcd(a,b)∣a∈A,b∈B\right\}$。

4 x v : 询问 $v$ 在集合 $x$ 中出现次数模 $2$ 的结果。

$1\leq n\leq 10^5,1\leq q\leq 10^6,1\leq v\leq 7000$。

Solution

对每个可重集 $i$ 开一个 $bitset$ : $a[i]$，$a[i][j]$ 表示第 $i$ 个集合中 $j$ 的倍数出现次数模 $2$。

1 x v ：用 $\mathcal O(\sqrt v)$ 的时间枚举 $v$ 的约数 $u$ 即可。

2 x y z ：$a[x]=a[y]\ \text{xor}\ a[z]$，$\text{xor}$ 可以理解为模 $2$ 意义下的加法。

3 x y z ：$a[x]=a[y]\ \text{and}\ a[z]$，$\text{and}$ 可以理解为模 $2$ 意义下的乘法。

4 x v ：设 $f(n)$ 表示 $n$ 在集合 $x$ 中的出现次数，$g(n)$ 表示 $n$ 的倍数在集合 $x$ 中的出现次数，那么有：$$g(n)=\sum_{n|d}f(d)⇔f(n)=\sum_{n|d}\mu(\frac{d}{n})g(d)$$

那么对每个数 $n$ 开一个 $bitset$ : $miu[n]$，其中 $miu[n][d]=\mu(\lfloor\frac{d}{n}\rfloor)\% 2$。

那么答案就是 $(a[x]\ \text{and}\ miu[v]).count()$ 模 $2$。

时间复杂度 $\mathcal O(q(\sqrt v+\frac{v}{64}))$。

#include <bits/stdc++.h>

using namespace std;

const int m = 7e3, e = 1e5 + 5, o = 7e3 + 5;
bitset<o>a[e], b[o];
int miu[o], n, q;
bool bo[o];

template <class t>
inline void read(t & res)
{
    char ch;
    while (ch = getchar(), !isdigit(ch));
    res = ch ^ 48;
    while (ch = getchar(), isdigit(ch))
    res = res * 10 + (ch ^ 48);
}

inline void init()
{
    int i, j;
    for (i = 1; i <= m; i++) miu[i] = 1;
    for (i = 2; i <= m; i++)
    if (!bo[i])
    {
        for (j = 2 * i; j <= m; j += i)
        {
            bo[j] = 1;
            if (j / i % i == 0) miu[j] = 0;
        }
    }
    for (i = 1; i <= m; i++)
    for (j = 1; i * j <= m; j++)
    b[i][i * j] = miu[j];
}

int main()
{
    int op, x, y, z, v, i;
    read(n); read(q);
    init();
    while (q--)
    {
        read(op);
        if (op == 1)
        {
            read(x); read(v); a[x].reset();
            int s = sqrt(v);
            for (i = 1; i <= s; i++)
            if (v % i == 0) a[x][i] = a[x][v / i] = 1;
        }
        else if (op == 2)
        {
            read(x); read(y); read(z);
            a[x] = a[y] ^ a[z];
        }
        else if (op == 3)
        {
            read(x); read(y); read(z);
            a[x] = a[y] & a[z];
        }
        else
        {
            read(x); read(v);
            putchar((((a[x] & b[v]).count()) & 1) + 48);
        }
    }
    return 0;
}