CF1097F Alex and a TV Show 题解 / 莫比乌斯反演学习笔记

zrl123456 · 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=\varnothing]

  这个容易证明，只需简单推导：

  \begin{aligned}\sum_{T\subseteq S}(-1)^T&=\sum_{len=0}^{|S|}(-1)^{len}\binom{|S|}{len}\\&=(-1+1)^{|S|}\\&=[len=0]\\&=[S=\varnothing]\end{aligned}

  :::: ::::: 不妨设 \displaystyle g_{i,j}=\begin{cases}\mu(\frac{j}{i})\bmod 2&i|j\\0&\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