动态 FMT

· · 算法·理论

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 问题考虑阈值分治。考察下述两个做法:

取阈值 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) 更优。