浅谈分治解决 0/1/? 匹配

starish · 2026-09-24 13:49:14 · 算法·理论

1. 静态离线

问题描述

给定 N 个精确 0/1 模式串，回答 Q 个包含 0/1/? 的查询串，位宽均为 K。求与每个查询串匹配的模式串权值和。

查询串的字符集只有 ?、0、1 三类，位权总和恒为 K。

用 SOS DP 处理以下数组：

查询分类

设查询串的固定 1 集合为 M_1，固定 0 集合为 M_0，通配集合为 M_?，U = \overline{M_0}。匹配条件为 M_1 \subseteq x \subseteq U。

1. cnt(?) \le K/3：\text{Ans} = \sum_{s \subseteq M_?} b[M_1 \mid s]
2. cnt(0) \le K/3（对 0 容斥，查超集）：\text{Ans} = \sum_{T \subseteq M_0} (-1)^{|T|} S_{\text{sup}}[M_1 \mid T]
3. cnt(1) \le K/3（对 1 容斥，查子集）：\text{Ans} = \sum_{T \subseteq M_1} (-1)^{|T|} S_{\text{sub}}[U \setminus T]

• 复杂度：时间 O(K \cdot 2^K + Q \cdot 2^{K/3})。

2. 动态在线

• 查询：给定包含自由位 W = x \oplus y 的通配区间 (x, y)，求已插入点中满足 m_1 \subseteq z 且 z \cap m_0 = \varnothing 的点权和；
• 插入：给定精确 0/1 点 z 与权值 g，插入数据结构。

不可离线做全局 SOS DP，采用阈值 B = K/2 进行分治。

策略

(1) 插入按点权大小 |z| 分类

• 维护 b[z] \mathrel{+}= g：记录单点精确权值。
• 小点（|z| \le B）：枚举 z 的子集更新 G：\forall U \subseteq z,\quad G[U] \mathrel{+}= g
• 大点（|z| > B）：补集 \overline{z} 满足 |u| < B，枚举 \overline{z} 的子集更新 H：\forall V \subseteq \overline{z},\quad H[V] \mathrel{+}= g

(2) 查询按自由位 |W| 分类

• |W| \le B：自由位极少，直接枚举 W 的子集查 b：

  \text{Ans} = \sum_{s \subseteq W} b[s \mid m_1]

• |W| > B：确定位极少，对小点和大点分别容斥：

  \text{Ans} = \underbrace{\sum_{T \subseteq m_0} (-1)^{|T|} G[m_1 \mid T]}_{\text{小点贡献}} + \underbrace{\sum_{T \subseteq m_1} (-1)^{|T|} H[m_0 \mid T]}_{\text{大点贡献}}

• 插入与查询枚举的子集大小均 \le 2^{B}；

• 复杂度：O(N\sqrt{V})；

实际上有 O(N(\frac{4}{3})^{K}) 的做法，个人认为本做法更加简单直观且卡常后也可通过例题。

3. 例题

1. 毒蛇越狱
2. Triples