快速子集变换（Fast Subset Transform，FST/FWT）：对长度为 2^n 的位集函数执行子集/超集 Zeta/Möbius 变换，以及按位 OR/AND/XOR 的快速沃尔什–阿达玛变换，用于子集卷积与集合并运算。复杂度 O(n·2^n)。
Description: Fast transforms on subset-indexed arrays of length 2^n:
- Subset/Superset Zeta and Möbius (inverse) transforms
- Bitwise OR/AND/XOR convolutions via FWT (Walsh–Hadamard) Time: O(n·2^n) Status: tested
-
函数/接口（据实现）
- subsetZeta(f): 对每一位 i，若掩码有第 i 位，则 f[S] += f[S\{i}]（子集求和）。
- subsetMobius(f): 上述逆变换，若掩码有第 i 位：f[S] -= f[S\{i}]。
- supersetZeta(f): 对每一位 i，若掩码无第 i 位，则 f[S] += f[S∪{i}]（超集求和）。
- supersetMobius(f): 上述逆变换，若掩码无第 i 位：f[S] -= f[S∪{i}]。
- fwt_or(a, inverse=false): OR 变换；对块大小 2、4…，成对 (x,y)→(x+y, y)；逆： (x,y)→(x−y, y)。
- fwt_and(a, inverse=false): AND 变换；成对 (x,y)→(x, x+y)；逆： (x,y)→(x, y−x)。
- fwt_xor(a, inverse=false): XOR 变换；成对 (x,y)→(x+y, x−y)；逆同式但最后整体除以 2（模域需乘 inv2）。
- conv_or(a,b): fwt_or(a); fwt_or(b); 逐点乘；逆 fwt_or。
- conv_and(a,b): 同上使用 AND 版。
- conv_xor(a,b): 同上使用 XOR 版（逆阶段每点乘 inv2^k，其中 k 为应用层数；迭代实现常在末端整体乘 inv(n)）。
-
子集/超集 Zeta/Möbius（子集 DP 常用）
- 设 f[S] 为集合函数：
- 子集 zeta：F[S] = Σ_{T⊆S} f[T]
- 子集 mobius：f[S] = Σ_{T⊆S} μ(T,S)·F[T]，迭代实现即“减去来源”。
- 超集版本将 Σ_{S⊆T} 等价地在位意义上反向扫描实现。
- 设 f[S] 为集合函数：
-
按位卷积（OR/AND/XOR）
- 目标：c[S] = Σ a[A]·b[B]，其中：
- OR 卷积：A OR B = S
- AND 卷积：A AND B = S
- XOR 卷积：A XOR B = S
- 做法：对 a,b 做相应 FWT，逐点相乘，再做逆变换即可。
- 目标：c[S] = Σ a[A]·b[B]，其中：
-
输出语义
- Zeta/Möbius：原地修改 f；可拷贝后返回新序列。
- conv_*：返回长度为 2^n 的卷积序列，语义如上。
-
复杂度
- 每个维度一趟扫描，总体 O(n·2^n)；空间原地/线性。
-
使用与注意
- 长度必须是 2^n；n 为位数（最大元素位宽）。
- 模运算：
- XOR 逆变换需要除以 2：模 p 下须乘 inv2（见 088-数论-模逆）；多层变换整体乘 inv(2^layers)。
- 建议统一在模 p（如 998244353）下运算，防止溢出。
- 实数/整数：
- 整数 OR/AND 卷积不涉及除法，直接运算即可。
- XOR 用整数需保证可整除（或在模域中进行）。
- 与 NTT/FFT 的关系：
- FWT 作用于“按位合并”的群，适用于集合并运算；多项式卷积优先用 098-数值算法-快速傅里叶变换 或 099-数值算法-模域FFT。
- 子集卷积（subset convolution）可用子集 zeta 在每个子集大小层面做卷积，或用 O(n^2·2^n) 的分层技巧（视题意与模板支持）。