Description

Link：CF1097F

Solution

注意到 $v \leq 7000$ 很小。设 $a[x][v]$ 表示集合 $x$ 中，$v$ 的倍数的出现次数 mod 2 的值。使用 std::bitset 来维护 $a[x]$。

• 1 x v：枚举 $v$ 的因数更新 $a[x]$ 即可。
• 2 x y z：$a[x] \gets a[y] \mathbin{\mathrm{xor}} a[z]$。
• 3 x y z：$a[x] \gets a[y] \mathbin{\mathrm{and}} a[z]$。
• 4 x v：设 $f(v)$ 表示 $v$ 的倍数的出现次数，设 $g(v)$ 表示 $v$ 的出现次数，则

$$f(v) = \sum\limits_{v \mid d} g(d) \iff g(v) = \sum\limits_{v \mid d} f(d) \mu\left( \frac{d}{v} \right)$$

对每个数 $v$ 再开个 std::bitset $h[v]$，其中 $h[v][v \cdot d] = \mu(d) \bmod 2$。答案即为 $(a[x] \mathbin{\mathrm{and}} h[v]).\mathrm{count}() \bmod 2$。

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