类子集和问题优化需求：N≤3×10^5的子集计数求解

问题描述 #

给定1≤N≤3×10^5，需统计集合{1,2,…,N-1}中所有和为N的子集数量。原实现采用基于有序map的记忆化递归（DP+容斥思想），仅能处理N≤10000的场景：N=3000时耗时约22秒，N超过10000出现段错误（推测为大整数存储与map冲突导致），需优化以支持更大N。

原实现代码 #

#include <iostream>
#include <chrono>
#include <map>
#include "bigint.h"

using namespace std;

// 二维哈希表存储递归结果：键为(i, sum)，值为计数
map<pair<int, int>, bigint> hmap;

bigint counter(int n, int i, int sum){

    // 终止条件：遍历完所有元素
    if(i == 0){ 
        if(sum == 0){
            return 1;
        }
        return 0;
    }

    // 提前终止：已凑出目标和
    if(sum == 0){
        return 1;
    }

    // 记忆化查询：已计算过的状态直接返回
    if(hmap.find(make_pair(i, sum)) != hmap.end()){
        return hmap[make_pair(i, sum)];
    }

    // 剪枝：当前元素大于剩余和，只能跳过
    if(sum - i < 0){
        return hmap[make_pair(i, sum)] = counter(n, sum, sum);
    }
    else{
        // 递归分支：包含当前元素 / 不包含当前元素
        return hmap[make_pair(i, sum)] = counter(n, i - 1, sum - i) + counter(n, i - 1, sum);
    }
}

初始调用参数为counter(N, N-1, N)。

优化方案 #

1. 转换为整数分拆问题，用数学公式替代DP #

该问题等价于：统计**将N拆分为不同正整数（且每个数≤N-1）**的方案数。而这个值等于「N的不同整数拆分方案数」减去1（减去仅包含N本身的拆分，因为N不在集合{1,..,N-1}中）。

利用五边形数定理可高效计算N的不同拆分方案数，时间复杂度为O(N√N)，空间复杂度O(N)，完全支持N=3×10^5的场景。

五边形数定理核心：

• 生成函数∏_{k=1}^∞ (1+x^k) = ∑_{m=-∞}^∞ (-1)^m x^{m(3m-1)/2}
• 递推公式：p_distinct(n) = ∑_{m≠0} (-1)^{m+1} p_distinct(n - g(m))，其中g(m)为五边形数（g(m)=m(3m-1)/2，m取正负整数），仅当n - g(m) ≥0时参与计算。

2. 替换大整数存储方式，避免map冲突 #

原代码用map存储大整数易引发内存管理问题，改用数组存储大整数，同时自定义轻量型大整数实现（仅需支持加减操作），避免第三方库冲突。

3. 迭代式递推替代递归 #

用迭代方式实现五边形数定理的递推逻辑，消除递归栈开销，进一步提升效率。

优化后示例代码 #

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 自定义大整数：低位存储在vector前端
struct BigInt {
    vector<int> digits;

    BigInt() {}
    BigInt(long long num) {
        if (num == 0) digits.push_back(0);
        while (num > 0) {
            digits.push_back(num % 10);
            num /= 10;
        }
    }

    // 大整数加法
    BigInt operator+(const BigInt& other) const {
        BigInt res;
        int carry = 0;
        int max_len = max(digits.size(), other.digits.size());
        for (int i = 0; i < max_len || carry; ++i) {
            int sum = carry;
            if (i < digits.size()) sum += digits[i];
            if (i < other.digits.size()) sum += other.digits[i];
            res.digits.push_back(sum % 10);
            carry = sum / 10;
        }
        return res;
    }

    // 大整数减法（确保this >= other）
    BigInt operator-(const BigInt& other) const {
        BigInt res;
        int borrow = 0;
        for (int i = 0; i < digits.size(); ++i) {
            int sub = digits[i] - borrow;
            if (i < other.digits.size()) sub -= other.digits[i];
            if (sub < 0) {
                sub += 10;
                borrow = 1;
            } else {
                borrow = 0;
            }
            res.digits.push_back(sub);
        }
        // 移除前导零
        while (res.digits.size() > 1 && res.digits.back() == 0) {
            res.digits.pop_back();
        }
        return res;
    }

    // 比较大小：this >= other
    bool operator>=(const BigInt& other) const {
        if (digits.size() != other.digits.size()) {
            return digits.size() > other.digits.size();
        }
        for (int i = digits.size() - 1; i >= 0; --i) {
            if (digits[i] != other.digits[i]) {
                return digits[i] > other.digits[i];
            }
        }
        return true;
    }

    // 打印大整数
    void print() const {
        for (int i = digits.size() - 1; i >= 0; --i) {
            cout << digits[i];
        }
        cout << endl;
    }
};

int main() {
    int n;
    cin >> n;

    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }

    // 生成所有不超过n的五边形数
    vector<int> pentagonal;
    for (int m = 1; ; ++m) {
        int g1 = m * (3 * m - 1) / 2;
        if (g1 > n) break;
        pentagonal.push_back(g1);
        int g2 = m * (3 * m + 1) / 2;
        if (g2 > n) break;
        pentagonal.push_back(g2);
    }

    // dp[i]表示i的不同整数拆分方案数
    vector<BigInt> dp(n + 1);
    dp[0] = BigInt(1);

    for (int i = 1; i <= n; ++i) {
        BigInt sum(0);
        int sign = 1; // 交替加减，每两个五边形数切换符号
        int idx = 0;
        while (idx < pentagonal.size() && pentagonal[idx] <= i) {
            if (sign == 1) {
                sum = sum + dp[i - pentagonal[idx]];
            } else {
                if (dp[i - pentagonal[idx]] >= sum) {
                    sum = dp[i - pentagonal[idx]] - sum;
                } else {
                    cerr << "计算异常：出现负数结果" << endl;
                    return 1;
                }
            }
            idx++;
            if (idx % 2 == 0) sign *= -1;
        }
        dp[i] = sum;
    }

    // 最终结果 = 拆分方案数 - 1（减去仅包含n本身的拆分）
    BigInt ans = dp[n] - BigInt(1);
    ans.print();

    return 0;
}

方案说明 #

• 时间复杂度O(N√N)，空间复杂度O(N)，可轻松处理N=3×10^5的场景；
• 自定义大整数实现避免了第三方库的内存冲突问题；
• 核心逻辑基于五边形数定理，彻底摆脱了原DP方案的O(N²)时间瓶颈。

内容的提问来源于stack exchange，提问作者svok