每日算法 — 使用java实现高维前缀和：SOS动态规划与子集卷积优化

算法概述

高维前缀和（Sum Over Subsets DP，简称SOS DP）是一种高效处理子集枚举问题的动态规划技术。对于 $n$ 维二进制空间，它能够在 $O(n \cdot 2^n)$ 时间内预处理所有子集的和，相比暴力的 $O(3^n)$ 方法实现了质的飞跃。SOS DP 在容斥原理、子集卷积、位运算DP等问题中有着不可替代的作用。

核心思想

对于一个集合 $S$，定义 $f(S)$ 为集合 $S$ 的某种属性值。高维前缀和计算的是：

$$F(S) = \sum_{T \subseteq S} f(T)$$

即对于每个集合 $S$，求出它所有子集 $T$ 的 $f(T)$ 之和。

递推思路

SOS DP 采用逐位填充的策略。设 $dp[i][mask]$ 表示只考虑前 $i$ 位时，$mask$ 的所有子集的和：

$$dp[i][mask] = \begin{cases} dp[i-1][mask] & \text{第 } i \text{ 位为0} \ dp[i-1][mask] + dp[i-1][mask \oplus 2^i] & \text{第 } i \text{ 位为1} \end{cases}$$

其中 $mask \oplus 2^i$ 是将第 $i$ 位从1变为0后的集合，即不包含第 $i$ 个元素的子集。

空间优化

由于 $dp[i]$ 只依赖于 $dp[i-1]$，可以使用滚动数组或原地更新，将空间优化到 $O(2^n)$。

Java 完整实现

import java.util.*;

/**
 * 高维前缀和（SOS DP）完整实现
 * 包含基础版本、超集版本、子集卷积等扩展
 */
public class SOSDP {

    /**
     * 基础SOS DP：计算每个mask的所有子集之和
     * f[mask] = sum of f[submask] for all submask ⊆ mask
     * 
     * @param f 原始数组，长度为 2^n
     * @param n 维度数（位数）
     * @return 高维前缀和数组
     */
    static long[] subsetSum(long[] f, int n) {
        long[] dp = f.clone();

        // 逐位处理：第i位表示是否包含元素i
        for (int i = 0; i < n; i++) {
            for (int mask = 0; mask < (1 << n); mask++) {
                // 如果第i位为1，则加上不含第i位的子集的值
                if ((mask & (1 << i)) != 0) {
                    dp[mask] += dp[mask ^ (1 << i)];
                }
            }
        }

        return dp;
    }

    /**
     * 超集版本：计算每个mask的所有超集之和
     * f[mask] = sum of f[supermask] for all supermask ⊇ mask
     */
    static long[] supersetSum(long[] f, int n) {
        long[] dp = f.clone();

        for (int i = 0; i < n; i++) {
            for (int mask = 0; mask < (1 << n); mask++) {
                // 如果第i位为0，则加上包含第i位的超集的值
                if ((mask & (1 << i)) == 0) {
                    dp[mask] += dp[mask | (1 << i)];
                }
            }
        }

        return dp;
    }

    /**
     * 子集卷积：计算 h[mask] = sum of f[s] * g[mask\s] for all s ⊆ mask
     * 其中 mask\s 表示 mask 中除去 s 的部分
     * 
     * 子集卷积的复杂度为 O(n^2 * 2^n)
     */
    static long[] subsetConvolution(long[] f, long[] g, int n) {
        // 按popcount（二进制中1的个数）分组
        long[][] fByPop = new long[n + 1][1 << n];
        long[][] gByPop = new long[n + 1][1 << n];

        for (int mask = 0; mask < (1 << n); mask++) {
            int pc = Integer.bitCount(mask);
            fByPop[pc][mask] = f[mask];
            gByPop[pc][mask] = g[mask];
        }

        // 对每组做SOS DP
        for (int pc = 0; pc <= n; pc++) {
            fByPop[pc] = subsetSum(fByPop[pc], n);
            gByPop[pc] = subsetSum(gByPop[pc], n);
        }

        // 逐点相乘：h_k[mask] = sum of f_i[mask] * g_{k-i}[mask]
        long[][] hByPop = new long[n + 1][1 << n];
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int k = 0; k <= n; k++) {
                for (int i = 0; i <= k; i++) {
                    hByPop[k][mask] += fByPop[i][mask] * gByPop[k - i][mask];
                }
            }
        }

        // Möbius反演（逆SOS DP）恢复结果
        long[] result = new long[1 << n];
        for (int pc = 0; pc <= n; pc++) {
            for (int i = 0; i < n; i++) {
                for (int mask = 0; mask < (1 << n); mask++) {
                    if ((mask & (1 << i)) != 0) {
                        hByPop[pc][mask] -= hByPop[pc][mask ^ (1 << i)];
                    }
                }
            }
        }

        for (int mask = 0; mask < (1 << n); mask++) {
            result[mask] = hByPop[Integer.bitCount(mask)][mask];
        }

        return result;
    }

    /**
     * 容斥原理应用：利用SOS DP快速计算
     * 求有多少个mask满足某种性质，可以通过容斥 + SOS DP 高效求解
     */
    static long[] inclusionExclusion(long[] f, int n) {
        // 先求SOS和
        long[] sos = subsetSum(f, n);

        // 容斥：g[mask] = sum of (-1)^(|mask| - |submask|) * f[submask]
        // 等价于在SOS基础上做Möbius变换
        long[] g = sos.clone();
        for (int i = 0; i < n; i++) {
            for (int mask = 0; mask < (1 << n); mask++) {
                if ((mask & (1 << i)) != 0) {
                    g[mask] -= g[mask ^ (1 << i)];
                }
            }
        }

        return g;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("=== 高维前缀和（SOS DP）演示 ===\n");

        // 示例：n=3，共8个集合
        int n = 3;
        long[] f = new long[1 << n];

        System.out.println("请输入8个整数（对应mask 000到111的值）：");
        for (int i = 0; i < (1 << n); i++) {
            f[i] = sc.nextLong();
        }

        // 计算子集和
        long[] subsetSum = subsetSum(f, n);
        System.out.println("\n子集和结果（每个mask的所有子集之和）：");
        for (int mask = 0; mask < (1 << n); mask++) {
            System.out.printf("mask=%d: F[%s] = %d%n", 
                mask, String.format("%3s", Integer.toBinaryString(mask)).replace(' ', '0'), 
                subsetSum[mask]);
        }

        // 计算超集和
        long[] supersetSum = supersetSum(f, n);
        System.out.println("\n超集和结果（每个mask的所有超集之和）：");
        for (int mask = 0; mask < (1 << n); mask++) {
            System.out.printf("mask=%d: G[%s] = %d%n", 
                mask, String.format("%3s", Integer.toBinaryString(mask)).replace(' ', '0'), 
                supersetSum[mask]);
        }

        // 子集卷积示例
        System.out.println("\n子集卷积演示（h = f * g）：");
        long[] g = {1, 2, 3, 4, 5, 6, 7, 8};
        long[] conv = subsetConvolution(f, g, n);
        for (int mask = 0; mask < (1 << n); mask++) {
            System.out.printf("h[%s] = %d%n", 
                String.format("%3s", Integer.toBinaryString(mask)).replace(' ', '0'), 
                conv[mask]);
        }
    }
}

复杂度分析

与暴力 $O(3^n)$ 相比，SOS DP 的 $O(n \cdot 2^n)$ 是一个巨大的改进：
– 当 $n = 20$ 时，$3^{20} \approx 3.5 \times 10^9$，而 $20 \cdot 2^{20} \approx 2 \times 10^7$

经典应用场景

1. 子集计数问题：统计有多少集合满足给定性质，利用容斥 + SOS DP
2. 位运算DP优化：如”子集选取”类问题的状态转移优化
3. 子集卷积：计算两个集合函数的卷积，用于组合数学问题
4. 超图计数：利用高维前缀和快速计算超边覆盖信息
5. GCD/LCM卷积：结合质因数分解，利用SOS DP处理GCD卷积

扩展：GCD卷积示例

/**
 * GCD卷积：h[n] = sum of f[d] * g[n/d] for all d | n
 * 通过质因数分解转化为SOS DP问题
 */
static long[] gcdConvolution(long[] f, long[] g, int maxN, int[] spf) {
    // spf为最小质因子数组
    // 实现略，核心思想是将每个数表示为质因数的指数向量
    // 然后利用SOS DP处理各质因数上的max/min操作
    return new long[maxN + 1];
}

SOS DP 是处理位运算和子集相关问题的强大工具，掌握它将为解决复杂组合问题打开新的大门。