P10009 [集训队互测 2022] 线段树 题解 / 关于组合数奇偶性判定的定理学习笔记
zrl123456
·
·
题解
:::::info[题目基本信息]
考察：分块，Lucas 定理，动态规划 DP（NOI/NOI+/CTSC）。
题目简介：
给定 \{a_n\}，q+n 次操作，操作分为两类：
- 给定 l,r，进行操作 \forall i\in(l,r]，同时令 a_i\leftarrow a_i\oplus a_{i-1}。
- 给定 pos，求 a_{pos} 的值。
其中操作满足条件：\forall i\in[1,n]，第 q+i 次操作都是第二种操作，且 pos=i。
数据范围：
-
-
-
- 对于第一种操作，1\le l\le r\le n。
- 对于第二种操作，1\le pos\le n。
时间限制：3s。
空间限制：512MB。
:::::
:::::info[闲话]
KSCD 太巨了！
本题解有借鉴其题解相关内容。
:::::
通过观察数据范围，是 10^5 量级的，然后开了 3s，猜测是根号复杂度带个 \log，同时莫队没有什么好突破，所以开始想分块。
同时如果对序列分块的话可能会有多次第一种操作导致影响力超过 \Theta(1) 个块，所以考虑同时对序列和操作分块。
根据上述，我们设阈值为 B，对序列每 B 个分一块，当第一次操作数达到 B 时分一块，这样保证了影响力只会在相邻两个块间产生，那么我们做的时候就会简单一点。
现在我们考虑如何快速计算它们多次异或后的值，容易发现若进行了 d 次操作，那么 a'_j（多次操作前的 a_j）会贡献到 a_i 这个地方 \dbinom{d}{i-j} 次，现在需要判断这个值的奇偶性。
:::::success[引理]{open}
当且仅当二进制下 y\subseteq x 时，\dbinom{x}{y} 为奇数。
:::::
:::::success[证明]
由 Lucas 定理：
\binom{x}{y}\equiv\binom{\lfloor\frac{x}{p}\rfloor}{\lfloor\frac{y}{p}\rfloor}\binom{x\bmod p}{y\bmod p}\pmod p
其中 p 是质数。
当 p=2 时，我们得到：
\binom{x}{y}\equiv\prod_{i=0}\binom{x_i}{y_i}\pmod 2
其中 x_i,y_i 分别代表 x 和 y 在二进制下第 i 位的值。
注意到 \dbinom{0}{0}=\dbinom{1}{0}=\dbinom{1}{1}=1，只有 \dbinom{0}{1}=0，所以最终容易得到原引理。
证毕。
:::::
所以通过上面的引理我们得到：
a_i=\bigoplus_{i-j\subseteq d}a'_j
这个式子可以使用 SOS DP 进行计算。
那么计算后有什么用呢？
具体地，我们对于相邻两个块，当这个操作是第一种操作且操作完全覆盖这两个块的时候我们令 d\leftarrow d+1，否则我们通过 SOS DP 直接清空标记然后对块内的数暴力进行操作即可。对于查询我们可以直接枚举子集计算。
这样复杂度是否正确？
对于每个第一种操作，容易发现被暴力计算的块最多只有 4 个，所以暴力计算这部分的复杂度是 \Theta(qB)，同时在清空标记时会有 \Theta(qB\log B) 的复杂度，查询时枚举子集会有 \Theta(qB) 的复杂度，同时每个操作块结束时需要下放标记，会有 \Theta(\dfrac{nq\log B}{B})，所以总复杂度是 \Theta(\dfrac{nq\log B}{B}+qB\log B)，取 B=\sqrt n 可得到 \Theta(q\sqrt n\log n) 的复杂度。
时间复杂度为 \Theta(q\sqrt n\log n)，空间复杂度为 \Theta(n+q)。
code