本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-19 21:14:44

:::::info[题目基本信息] 考察：莫比乌斯反演，bitset（$2500$）。
题目简介：
给定 $n$ 个可重集 $\{S_n\}$，初始均为空，有 $q$ 次操作，分为 $4$ 种：

1. 给定 $x,v$，进行操作 $S_x\leftarrow v$。
2. 给定 $x,y,z$，进行操作 $S_x\leftarrow S_y\cup S_z$。
3. 给定 $x,y,z$，进行操作 $S_x\leftarrow\{ab|a\in S_y,b\in S_z\}$。
4. 给定 $x,v$，求 $(\sum_{p\in S_x}[p=v])\bmod 2$。

数据范围：

• $1\le n\le 10^5$
• $1\le q\le 10^6$
• $1\le x,y,z\le n$
• $1\le v\le 7000$ ::::: 注意到最终求的是出现次数 $\bmod\ 2$ 的值，值域又只有 $7000$，所以我们可以考虑使用 bitset 维护每一个可重集，这样全都变成了普通集合（仍设为 $\{S_n\}$），最后的结果就是一个数是否普通集合中出现，这样操作 1,2,4 都好维护，但操作 3 不好维护。
  这时我们将操作 3 暴力计算的式子列出来观察推导一波（设 $a_{x,v}$ 为 $S_x$ 中 $v$ 的是否出现，出现为 $1$，未出现为 $0$）：
  $$\begin{aligned}a_{x,v}&=(\sum_{p\in S_y}\sum_{q\in S_z}[\gcd(p,q)=v])\bmod 2\&=(\sum_p\sum_qa_{y,p}a_{z,q}[\gcd(p,q)=v])\bmod 2\&=(\sum_{v|p}\sum_{v|q}a_{y,p}a_{z,q}[\gcd(p,q)=v])\bmod 2\end{aligned}$$ 所以我们转化需要维护的东西，设 $\displaystyle b_{x,v}=(\sum_{v|i}a_{x,i})\bmod 2$，那么我们对于每个操作看看它们能否维护。

操作 1：

由题可知此时仅有 $a_{x,v}=1$，那么 $b_{x,i}=1$ 当且仅当 $i|v$，对于每个 $v$ 预处理一下直接给 bitset 赋值即可。

操作 2：

推导：
$$\begin{aligned}b_{x,v}&=(\sum_{v|i}a_{x,i})\bmod 2\&=(\sum_{v|i}(a_{y,i}+a_{z,i})\bmod 2)\bmod 2\&=((\sum_{v|i}a_{y,i})+(\sum_{v|i}a_{z,i}))\bmod 2\&=(b_{y,v}+b_{z,v})\bmod 2\end{aligned}$$ 所以在 bitset 维护的时候直接异或起来即可。

操作 3：

推导：
$$\begin{aligned}b_{x,v}&=(\sum_{v|i}a_{x,i})\bmod 2\&=(\sum_{v|i}(\sum_{i|p}\sum_{i|q}a_{y,p}a_{z,q}[\gcd(p,q)=i])\bmod 2)\bmod 2\&=(\sum_{v|p}\sum_{v|q}\sum_{v|i}[i|p\land i|q\land \gcd(p,q)=i]a_{y,p}a_{z,q})\bmod 2\&=(\sum_{v|p}\sum_{v|q}a_{y,p}a_{z,q})\bmod 2\&=b_{y,v}b_{z,v}\bmod 2\end{aligned}$$ 所以在 bitset 维护的时候直接按位与起来即可。

操作 4：

现在我们已知 $\{b_x\}$，要反推 $a_{x,v}$。
根据莫比乌斯反演：
$$a_{x,v}=(\sum_{v|i}b_x\mu(\frac{i}{v}))\bmod 2$$ :::::success[证明] 对上式做等价转化：
$$\begin{aligned}a_{x,v}&=(\sum_{v|i}b_x\mu(\frac{i}{v}))\bmod 2\&=(\sum_{v|i}(\sum_{i|j}a_{x,j})\mu(\frac{i}{v}))\bmod 2\&=(\sum_{v|j}a_{x,j}\sum_{v|i,i|j}\mu(\frac{i}{v}))\bmod 2\&=(\sum_{v|j}a_{x,j}\sum_{i|\frac{v}{j}}\mu(i))\bmod 2\end{aligned}$$ 现在只需要证明（莫比乌斯反演）：
$$\sum_{i|n}\mu(i)=[n=1]$$ ::::success[莫比乌斯反演证明] 设 $\displaystyle n=\prod_{i=1}^mp_i^{k_i}$（即 $n$ 的唯一分解形式），那么我们得到上式中 $\mu(i)\ne 0$ 的条件是 $i|\displaystyle\prod_{i=1}^mp_i^{\min(1,k_i)}$，这个容易分析，那么 $i$ 都可以表示成若干个不同质数的乘积 $S=\displaystyle\bigcup_{i=1}^m\{p_i\}$，那么上式转化为：
$$\sum_{T\subseteq S}(-1)^T=[S=\arnothing]$$ 这个容易证明，只需简单推导：
$$\begin{aligned}\sum_{T\subseteq S}(-1)^T&=\sum_{len=0}^{|S|}(-1)^{len}\binom{|S|}{len}\&=(-1+1)^{|S|}\&=[len=0]\&=[S=\arnothing]\end{aligned}$$ :::: ::::: 不妨设 $\displaystyle g_{i,j}=\begin{cases}\mu(\frac{j}{i})\bmod 2&i|j\&\text{otherwise}\end{cases}$，那么上式可以改写为：
$$a_{x,v}=(\sum_ib_xg_{v,i})\bmod 2$$ 这个直接预处理 $g$ 然后在询问时将 $b_x$ 和 $g_v$ 两个 bitset 按位与后调用 count 函数即可。

时间复杂度为 $\Theta(V\ln V+\dfrac{qV}{w})$（由于我实现的不太好所以实际是 $\Theta(V^2+\dfrac{qV}{w})$ 的），空间复杂度为 $\Theta(V+\dfrac{V^2+nV}{w})$。

code