动态 FMT
stripe_python
·
·
算法·理论
P10408 「SMOI-R1」Apple。
维护映射 f : 2^U \to \mathbb{N},其中 U=\{0,1,\cdots,n-1\}。进行 q 次操作:
- 给定 S,查询 \sum \limits_{T \subseteq S} f_T。
- 给定 S,x,令 f_S \gets x。
高低位分治
动态 FMT 问题考虑阈值分治。考察下述两个做法:
- 修改单点改,询问枚举子集,复杂度 O(1) - O(2^n)。
- 修改求 FMT 增量,询问单点查,复杂度 O(2^n)-O(1)。
取阈值 k=\lfloor n/2 \rfloor,对低 k 位 FMT,高 k 位枚举子集。
具体地,将集合 S \subseteq U 表示为二元组 S=(S_0,S_1),其中 S_0=S \cap [0,k), S_1=S \cap [k,n)。维护
g_{S}=\sum_{T \subseteq S} [S_0=T_0] f_T
修改枚举 S_0' \supseteq S_0 更新 f_{(S_0',S_1)} \gets \delta,查询枚举 \sum \limits_{S_1' \subseteq S_1} f_{(S_0,S_1')} 即可。
复杂度平衡到 O(q 2^{n/2}) 可以通过。代码。
观虫我
观察 FMT 位矩阵 Z=\begin{bmatrix}1&0\\1&1\end{bmatrix},分解出 Z=BA。修改时保存中间状态 A \vec{x},查询再复合 B \times A \vec{x}。
高低位分治取两个平凡分解
Z=IZ=ZI, I=\begin{bmatrix}1&0\\0&1\end{bmatrix}
容易发现 IZ, ZI 的分解对每个 x \in U 独立。观虫我指出,存在非平凡分解
Z=\begin{bmatrix}1&-1\\1&0\end{bmatrix}
\begin{bmatrix}1&1\\0&1\end{bmatrix}
对应修改时 0 \to 0, 1\to 0/1,查询时 0 \to 0/1, 1\overset{-1}{\to} 0。对所有 x \in U 使用上述分解得到子集反演
g_S=\sum_{S \subseteq T} f_T \iff f_S=\sum_{T \supseteq S} (-1)^{|T|-|S|} g_T
枚举 A=T \setminus S 则 f_S=\sum \limits_{A \cap T=\varnothing} (-1)^{|A|} g_A。
对每个 x \in U 独立随机选择三种分解之一,修改查询视情况选择。
对修改查询过程分析,易得期望分支数 \frac{4}{3},期望复杂度 O(q (4/3)^n) 更优。