简单dp

题意分析

给定一个包含 N 个正整数的序列 A 和一个正整数 S，要求计算所有非空子集 T 的 f(T) 之和（模 998244353）。其中 f(T) 定义为 T 的非空子集中和为 S 的子集个数。

关键思路

直接枚举所有非空子集 T 并计算 f(T) 是不可能的（因 N≤3000，子集数量为 23000 级）。需通过数学转化简化问题：

1.问题转化：总和等于所有 “和为 S 的非空子集 U” 被多少个 T 包含的数量之和。 对于每个和为 S 的非空子集 U，包含 U 的非空子集 T 的数量为 2N− abs(u)（abs(u)是 U 的大小，其余元素可自由选择是否加入 T）。

2.动态规划求解：需计算所有和为 S 的非空子集 U 的 2N− abs(u) 之和。 ·定义 dp[j] 为 “和为 j 的所有子集 U 的 2− abs(u) 之和”（2−1 模 998244353 为 499122177）。 ·最终结果为 dp[S]×2N mod 998244353（因 2N×2− abs(u) = 2N − abs(u)）。

算法步骤

1.预处理：计算 2N mod 998244353（记为 p2），以及 2−1 mod 998244353（即 499122177）。

2.初始化 DP：dp[0] = 1（空集的贡献基础），其余 dp[j] = 0。

3.更新 DP：对每个元素 ai，从 S 逆向遍历至 ai，更新 dp[j] += dp[j−a[i]]×499122177 mod 998244353（累加加入 ai 后的新子集贡献）。

4. 结果计算：最终答案为 dp[S]×p2 mod 998244353。

代码及注释

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
int main() {
    freopen("sample.in", "r", stdin);
    freopen("sample.out", "w", stdout);
    // 关闭cin与stdin的同步，加快输入速度
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, s;
    cin >> n >> s;
    // 存储物品的数组，下标从1开始方便处理
    vector<int> a(n + 5);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // 计算2^n mod MOD，用于最终结果的修正
    long long p2 = 1;
    for(int i = 1; i <= n; i++) {
        p2 = (p2 * 2) % MOD;
    }
    vector<long long> dp(s + 1, 0);
    dp[0] = 1;  // 初始化：和为0的方案数为1（不选任何物品）
    // 遍历每个物品，动态规划
    for(int i = 1; i <= n; i++) {
        // 逆序遍历确保每个物品只被考虑一次（01背包）
        for(int j = s; j >= 0; j--) {
            // 如果当前物品加入后总和不超过s，就更新
            if(j + a[i] > s) continue;
            // 499122177是2在模MOD下的逆元（2*499122177 mod MOD = 1）
            // 这里等价于dp[j] / 2，用于加权计算
            dp[j + a[i]] = (dp[j + a[i]] + dp[j] * 499122177) % MOD;
        }
    }
    // 最终答案：dp[s]乘以2^n mod MOD
    long long ans = (dp[s] * p2) % MOD;
    cout << ans; 
    return 0;
}

复杂度分析

· 时间复杂度：O(N×S)，其中 N 是序列长度，S 是目标和（均不超过 3000）。 · 空间复杂度：O(S)，仅需存储长度为 S + 1 的 dp 数组。