题目
划分
解题思路(01背包子集和模型)
题目关键特征
给定 40 个正整数，将其划分为两个非空子集，使得两子集元素和的乘积最大。
设总和为 total，若一个子集和为 s，则乘积为 s * (total - s)。
该函数在 s = total / 2 时取最大值 → 目标转化为：找出最接近 total/2 的可行子集和 s（0 < s < total）。
问题转化思路
- 物品：40 个数字，每个只能用一次
- 背包容量上限：
total（所有数之和，约 25 万） - 状态定义目标：判断某个和
s是否能被凑出 → 01 背包可行性问题（子集和） - 最终答案：枚举所有可达的
s，计算s * (total - s)的最大值
💡 为什么不能直接取
s = total/2？
因为不一定存在子集和恰好等于total/2，必须从实际可达的和中找最接近者。
动态规划设计
二维 DP 定义与转移
-
dp[i][j]：从前i个数中能否选出若干个，使其和恰好为j -
初始化：
dp[0][0] = true（0 个数可凑出和 0）dp[0][j>0] = false
-
递推公式：
dp[i][j] = dp[i-1][j] || (j >= nums[i-1] && dp[i-1][j - nums[i-1]])- 不选第
i个数 → 继承dp[i-1][j] - 选第
i个数 → 需j >= nums[i-1]且dp[i-1][j - nums[i-1]]为真
- 不选第
一维滚动数组优化
- 状态压缩：
dp[j]表示当前能否凑出和j - 遍历顺序：内层循环 倒序（
j从total到num）- 防止同一物品被重复使用（正序会导致完全背包）
- 初始化：
dp[0] = true，其余默认false
✅ 外层物品内层容量，倒序遍历保 01；初始
dp[0]=true，可行性靠||更新。
参考代码
方法一：二维 DP（清晰展示状态转移逻辑）
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int[] nums = {
5160, 9191, 6410, 4657, 7492, 1531, 8854, 1253, 4520, 9231,
1266, 4801, 3484, 4323, 5070, 1789, 2744, 5959, 9426, 4433,
4404, 5291, 2470, 8533, 7608, 2935, 8922, 5273, 8364, 8819,
7374, 8077, 5336, 8495, 5602, 6553, 3548, 5267, 9150, 3309
};
int n = nums.length;
// 计算总和作为背包容量上限
int total = 0;
for (int x : nums) total += x;
// dp[i][j]: 前i个数能否凑出和j
boolean[][] dp = new boolean[n + 1][total + 1];
dp[0][0] = true; // 基础情况：0个数凑0
// 状态转移：逐个考虑每个数字
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= total; j++) {
// 不选当前数字nums[i-1]
dp[i][j] = dp[i - 1][j];
// 选当前数字（需满足容量足够）
if (j >= nums[i - 1]) {
dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
// 枚举所有可行子集和s，求最大乘积
long ans = 0;
for (int s = 1; s < total; s++) { // 排除s=0或s=total（非空要求）
if (dp[n][s]) {
ans = Math.max(ans, (long) s * (total - s));
}
}
System.out.println(ans);
}
}
方法二：一维 DP（空间优化，推荐写法）
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int[] nums = {
5160, 9191, 6410, 4657, 7492, 1531, 8854, 1253, 4520, 9231,
1266, 4801, 3484, 4323, 5070, 1789, 2744, 5959, 9426, 4433,
4404, 5291, 2470, 8533, 7608, 2935, 8922, 5273, 8364, 8819,
7374, 8077, 5336, 8495, 5602, 6553, 3548, 5267, 9150, 3309
};
int n = nums.length;
int total = 0;
for (int x : nums) total += x;
// 一维dp: dp[j]表示能否凑出和j
boolean[] dp = new boolean[total + 1];
dp[0] = true; // 初始状态
// 01背包标准写法：外层物品，内层容量倒序
for (int num : nums) {
for (int j = total; j >= num; j--) {
// 若j-num可达，则j也可达
if (dp[j - num]) {
dp[j] = true;
}
}
}
// 找最大乘积
long ans = 0;
for (int s = 1; s < total; s++) {
if (dp[s]) {
ans = Math.max(ans, (long) s * (total - s));
}
}
System.out.println(ans);
}
}
📌 提交答案：运行任一代码输出结果为
12873625444，直接提交该整数即可。
砝码称重
解题思路(三态砝码动态规划)
题目关键特征
你有一架天平和 N 个砝码，重量依次是 W_1, W_2, \ldots, W_N 。每个砝码可以：
- 放在左边托盘（和被称物体同侧）→ 相当于 +W_i
- 放在右边托盘（和被称物体对侧）→ 相当于 -W_i
- 不使用 → 相当于 0
目标是：能称出多少种不同的正整数重量？
📌 注意：题目问的是“重量”，所以只统计 大于 0 的结果。
暴力 DFS 思路（理解用，效率低）
我们可以用递归枚举每个砝码的三种选择：
dfs(i, sum)表示处理到第i个砝码，当前总和为sum- 对每个砝码，有三种操作：
- 加：
dfs(i+1, sum + w[i]) - 减：
dfs(i+1, sum - w[i]) - 不选：
dfs(i+1, sum)
- 加：
- 当
i == n时，如果sum > 0，就把sum加入一个 Set 去重
但这种方法时间复杂度是 O(3^N) ，当 N = 30 时完全不可行。
所以我们需要用 动态规划 来高效解决。
动态规划核心思想
第一步：确定范围
设所有砝码总重量为 total = W₁ + W₂ + … + Wₙ。
那么所有可能的带符号和的范围是：
从 -total 到 +total，一共最多 2 * total + 1 种可能。
但数组下标不能是负数，所以我们引入一个偏移量（offset）：
- 令
offset = total - 真实和为
x→ 存储在数组下标j = x + offset处 - 例如：
- 真实和
-5→ 存在dp[total - 5] - 真实和
0→ 存在dp[total] - 真实和
+3→ 存在dp[total + 3]
- 真实和
这样就能用普通数组表示负数状态了。
第二步：二维 DP 设计（帮助理解）
- 定义
dp[i][j]：使用前i个砝码，是否能凑出 对应下标 j 的真实和（即真实和 =j - offset） - 初始化：
dp[0][offset] = true：0 个砝码只能凑出和为 0- 其他
dp[0][j] = false
- 状态转移（对第
i个砝码，重量为w = weights[i-1]）：- 如果
dp[i-1][j]为真，那么：- 不放：
dp[i][j] = true - 放左边（+w）：如果
j + w <= 2 * total，则dp[i][j + w] = true - 放右边（-w）：如果
j - w >= 0，则dp[i][j - w] = true
- 不放：
- 如果
最后，统计 j 从 offset + 1 到 2 * total 中 dp[n][j] == true 的个数，就是答案。
第三步：优化为一维 DP（实际写法）
因为每次只依赖上一轮的状态，我们可以用一维数组。
但注意：不能像 01 背包那样倒序更新！
因为这里每个状态会同时影响 j + w 和 j - w，如果直接在原数组修改，会导致同一个砝码被多次使用。
✅ 正确做法：每轮新建一个临时数组 newDp
步骤如下：
- 创建
dp数组，大小为2 * total + 1 dp[offset] = true（初始和为 0）- 对每个砝码
w：- 创建
newDp数组（全 false） - 遍历所有
j：- 如果
dp[j]为真，则：newDp[j] = true（不放）newDp[j + w] = true（放左边，+w）newDp[j - w] = true（放右边，-w）
- 如果
- 将
dp = newDp
- 创建
- 最后统计
j = offset + 1到2 * total中dp[j] == true的数量
参考代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] weights = new int[n];
int total = 0;
for (int i = 0; i < n; i++) {
weights[i] = sc.nextInt();
total += weights[i];
}
// dp[j] 表示是否能凑出“真实和 = j - total”
// 数组下标范围：0 ~ 2*total，共 2*total+1 个位置
boolean[] dp = new boolean[2 * total + 1];
int offset = total;
dp[offset] = true; // 初始状态：和为0可达
// 逐个处理每个砝码
for (int w : weights) {
boolean[] newDp = new boolean[2 * total + 1]; // 新建临时数组
for (int j = 0; j <= 2 * total; j++) {
if (!dp[j]) continue; // 当前状态不可达，跳过
// 三种选择
newDp[j] = true; // 不放
if (j + w <= 2 * total)
newDp[j + w] = true; // 放左边（+w）
if (j - w >= 0)
newDp[j - w] = true; // 放右边（-w）
}
dp = newDp; // 更新状态
}
// 统计所有正整数重量（真实和 > 0）
int count = 0;
for (int j = offset + 1; j <= 2 * total; j++) {
if (dp[j]) {
count++;
}
}
System.out.println(count);
}
}
关键细节说明
Q1：为什么只统计正数？
因为题目问的是“能称出多少种不同的重量”，重量必须是正数。负数只是中间计算状态，不代表实际可称的重量。
Q2：为什么需要偏移量？
Java 数组下标不能为负数。通过 offset = total，我们将区间 [-total, total] 平移到 [0, 2*total]，使得所有可能的和都能用非负下标表示。
Q3：为什么不能直接在原数组上更新？
因为每个砝码只能用一次。如果直接更新 dp[j + w] 或 dp[j - w]，后续遍历到这些位置时可能会再次使用同一个砝码，导致错误。用 newDp 能确保每轮只基于上一轮的完整状态进行转移。
Q4：时间复杂度如何？
- 总重量
total最大约为 10^5 （题目隐含） - 时间复杂度： O(N \times total)
- 空间复杂度： O(total)
- 对于 N \leq 30 ，完全可以在 1 秒内运行完毕
倒水
解题思路(分组背包)
本题要求在总水量不超过 m 的前提下，为 n 位客人分配倒水量，使得总满意度最大。每位客人有三种互斥的倒水策略：
- 倒水量
< a[i]→ 满意度为e[i] - 倒水量
= a[i]→ 满意度为b[i] - 倒水量
≥ c[i]→ 满意度为d[i]
由于每位客人只能选择一种策略，且策略之间互斥，这本质上是一个 分组背包问题：每组（客人）有三个物品（策略），每组至多选一个。
核心思想：默认选择 + 替换优化
我们采用一种巧妙的动态规划策略：
- 默认为当前客人选择“倒 0 毫升”（即满意度
e[i]），直接累加到当前状态； - 然后尝试用更优的选项（
b[i]或d[i]）替换这个默认选择。
这样，状态 dp[j] 始终表示：前 i 位客人，在总用水量恰好为 j 时的最大满意度。
为什么必须倒序遍历容量？
在状态转移中，我们需要用到上一轮（前 i-1 位客人）的状态：
dp[j] = max(dp[j], dp[j - a[i]] + b[i])
- 如果正序遍历，
dp[j - a[i]]可能已被当前轮加上了e[i]，导致同一个客人被重复计算（既算e[i]又算b[i]），违反“每组仅选一个”的规则。 - 倒序遍历保证
dp[j - vol]尚未被当前轮修改，仍是上一轮的纯净状态。
状态定义与转移
- 状态定义：
dp[j]表示总用水量为j时的最大满意度。 - 初始化：
dp[0...m] = 0，表示没有客人时满意度为 0。 - 状态转移（对每位客人
i）：dp[j] += e[i]：默认选择倒 0 毫升；- 若
j ≥ a[i]，尝试：dp[j] = max(dp[j], dp[j - a[i]] + b[i])； - 若
j ≥ c[i]，尝试：dp[j] = max(dp[j], dp[j - c[i]] + d[i])。
参考代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 客人数量
int m = sc.nextInt(); // 总水量上限
// 使用 1-indexed 数组便于理解
int[] a = new int[n + 1];
int[] b = new int[n + 1];
int[] c = new int[n + 1];
int[] d = new int[n + 1];
int[] e = new int[n + 1];
// 读入每位客人的五元组 (a, b, c, d, e)
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
b[i] = sc.nextInt();
c[i] = sc.nextInt();
d[i] = sc.nextInt();
e[i] = sc.nextInt();
}
// dp[j]: 总用水量为 j 时的最大满意度
// 初始化为 0: 没有客人时满意度为 0
long[] dp = new long[m + 1];
// 遍历每位客人 (分组)
for (int i = 1; i <= n; i++) {
// 倒序遍历水量 j, 防止同一客人被重复选择
for (int j = m; j >= 0; j--) {
// 默认策略: 倒 0 毫升, 满意度为 e[i]
dp[j] += e[i];
// 尝试策略2: 倒 a[i] 毫升
if (j >= a[i]) {
dp[j] = Math.max(dp[j], dp[j - a[i]] + b[i]);
}
// 尝试策略3: 倒 c[i] 毫升 (倒 >= c[i] 即可得 d[i], 但只需考虑最小消耗 c[i])
if (j >= c[i]) {
dp[j] = Math.max(dp[j], dp[j - c[i]] + d[i]);
}
}
}
long ans = dp[0];
for (int j = 1; j <= m; j++) {
if (dp[j] > ans) ans = dp[j];
}
System.out.println(ans);
}
}
背包与魔法
解题思路(背包问题进阶)
本题是经典的 01 背包问题的扩展，唯一区别在于：小蓝可以使用一次魔法，将某一件物品的重量增加 K，同时价值翻倍。
这引入了一个新的决策维度：是否使用魔法？用在哪个物品上？
核心思想：状态拆分 + 状态转移
由于魔法只能使用一次，我们可以将状态分为两类：
- 未使用魔法：当前背包容量为
j，前i个物品中尚未使用魔法的最大价值。 - 已使用魔法：当前背包容量为
j，前i个物品中已经使用过魔法的最大价值。
✅ 关键点：魔法只能用一次，所以一旦使用，后续物品不能再用。
状态定义
设 f[i][j][0] 表示考虑前 i 个物品、背包容量为 j 且尚未使用魔法时的最大价值；
设 f[i][j][1] 表示考虑前 i 个物品、背包容量为 j 且已经使用过魔法时的最大价值。
但为了节省空间，我们只需维护两个一维数组：f[j][0] 和 f[j][1]，分别表示当前状态。
状态转移（关键）
对每个物品 i，有三种情况：
- 物品无法放入背包：
w[i] > j→ 忽略 - 不选该物品：无论是否使用魔法，状态不变
- 选该物品：
- 若未使用魔法：可正常放入，价值为
v[i] - 若已使用魔法：可选择不用魔法（之前用过，这次正常放）或用魔法（之前没用过这次用）（重量变为
w[i]+k，价值变为2*v[i]）
- 若未使用魔法：可正常放入，价值为
⚠️ 注意：魔法只能用一次，所以一旦使用，后续物品不能再用。
状态转移方程
- 未使用魔法：
f[j][0] = max(f[j][0], f[j - w[i]][0] + v[i]) - 已使用魔法：
f[j][1] = max( f[j][1], // 不放 f[j - w[i]][1] + v[i], // 不用魔法放 f[j - (w[i] + k)][0] + 2 * v[i] // 用魔法放（从“未使用”状态转移） )
✅ 口诀：一个背包两种态，魔法只用一次；未用先放再用，已用可选可魔。
参考代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 物品数量
int m = sc.nextInt(); // 背包容量
int k = sc.nextInt(); // 魔法增重值
int[] w = new int[n + 1]; // 重量
int[] v = new int[n + 1]; // 价值
for (int i = 1; i <= n; i++) {
w[i] = sc.nextInt();
v[i] = sc.nextInt();
}
// dp[j][0]: 容量为 j 且未使用魔法的最大价值
// dp[j][1]: 容量为 j 且已使用魔法的最大价值
long[][] dp = new long[m + 1][2];
// 遍历每个物品
for (int i = 1; i <= n; i++) {
// 倒序遍历容量，防止重复选择
for (int j = m; j >= w[i]; j--) {
// 情况1: 未使用魔法，选择第 i 个物品
dp[j][0] = Math.max(dp[j][0], dp[j - w[i]][0] + v[i]);
// 情况2: 已使用魔法，选择第 i 个物品
// 子情况 a: 不用魔法放（正常放）
dp[j][1] = Math.max(dp[j][1], dp[j - w[i]][1] + v[i]);
// 子情况 b: 用魔法放（重量变为 w[i]+k，价值变为 2*v[i]）
if (j >= w[i] + k) {
dp[j][1] = Math.max(dp[j][1], dp[j - (w[i] + k)][0] + 2 * v[i]);
}
}
}
// 最终答案：取两种状态下的最大值
System.out.println(Math.max(dp[m][0], dp[m][1]));
}
}
健身
解题思路(区间连续任务背包模型)
本题看似是任务调度问题，实则可转化为 “区间选择型背包”：
每个健身计划是一个“物品”，其“重量”是连续的 2^k 天，“价值”是增益 s。
但与普通背包不同的是：物品只能放在特定位置（必须连续且空闲）。
问题建模：从任务调度到背包
- 容量：总天数
n - 物品：每个计划
(k, s)，占用len = 2^k天 - 约束：物品必须放在一段连续且完全空闲的区间内
- 目标：选择若干不重叠的物品，使总价值最大
✅ 关键转化：将“能否安排计划”转化为“该长度区间是否空闲”
状态定义
设 dp[i] 表示考虑前 i 天时能获得的最大增益。
状态转移
对每一天 i，我们有两种选择：
-
第 i 天不训练：
dp[i] = dp[i - 1] -
以第 i 天结尾完成一个计划：
枚举所有可能的计划长度len = 2^k，若区间[i - len + 1, i]全空闲，则：dp[i] = Math.max(dp[i], dp[i - len] + maxGain[k])
⚠️ 注意：同一个
k可能有多个计划，我们只需保留最大增益的那个（贪心优化）
如何快速判断区间是否空闲？
使用 前缀和数组 busy：
busy[i]表示前i天中有多少天被占用- 区间
[l, r]空闲 ⇨busy[r] - busy[l - 1] == 0
枚举优化
由于 2^k 随 k 指数增长，当 2^k > i 时可提前终止循环。
参考代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 总天数
int m = sc.nextInt(); // 健身计划数量
int q = sc.nextInt(); // 已有安排天数
// 标记被占用的日期 (1-indexed)
boolean[] occupied = new boolean[n + 1];
for (int i = 0; i < q; i++) {
int day = sc.nextInt();
occupied[day] = true;
}
// 构建前缀和: busy[i] = 前 i 天中被占用的天数
int[] busy = new int[n + 1];
for (int i = 1; i <= n; i++) {
busy[i] = busy[i - 1] + (occupied[i] ? 1 : 0);
}
// 对每个 k, 保存最大增益 (k 最大为 log2(n) ≈ 20)
long[] maxGain = new long[32]; // 2^30 > 1e9, 足够覆盖 n <= 2e5
Arrays.fill(maxGain, 0);
for (int i = 0; i < m; i++) {
int k = sc.nextInt();
long s = sc.nextLong();
if (s > maxGain[k]) {
maxGain[k] = s;
}
}
// dp[i]: 前 i 天的最大增益
long[] dp = new long[n + 1];
for (int i = 1; i <= n; i++) {
// 选择1: 第 i 天不训练
dp[i] = dp[i - 1];
// 选择2: 尝试以第 i 天结尾完成一个计划
for (int k = 0; k <= 31; k++) {
int len = 1 << k; // 计划所需天数 = 2^k
if (len > i) break; // 长度超过当前天数，后续 k 更大，直接退出
int start = i - len + 1; // 区间起始日
// 判断 [start, i] 是否全空闲
if (busy[i] - busy[start - 1] == 0) {
dp[i] = Math.max(dp[i], dp[i - len] + maxGain[k]);
}
}
}
System.out.println(dp[n]);
}
}
买书
解题思路(计数型完全背包)
本题是经典的 完全背包问题 的变形，目标不是求最大价值，而是求 恰好花完 n 元的不同方案数。
问题建模：从“选物品”到“计方案”
- 物品：四种书籍，价格分别为
10, 20, 50, 100 - 容量：总钱数
n - 限制：每种书可以购买多次（完全背包）
- 目标：求恰好花完
n元的方案总数
✅ 关键点：状态转移表示“增加一种选择”带来的方案数变化
状态定义
设 dp[j] 表示花掉 j 元钱时的不同买书方案数。
初始状态
dp[0] = 1：花 0 元有一种方案 —— 什么都不买- 其余
dp[j] = 0
状态转移
对于每种书（价格为 p），我们有：
dp[j] += dp[j - p]
含义：当前方案数 = 不选这本书 + 选这本书
dp[j]：不选这本书的方案数（原值）dp[j - p]：选这本书的方案数（即在j-p元的基础上再买一本）
注意：必须正序遍历！
因为完全背包允许重复选择，所以要 从小到大遍历容量，确保每个物品被多次使用。
参考代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 总钱数
// 四种书的价格
int[] price = {10, 20, 50, 100};
// dp[j]: 花 j 元的不同方案数
long[] dp = new long[n + 1];
dp[0] = 1; // 花 0 元有一种方案：什么都不买
// 枚举每种书
for (int i = 0; i < price.length; i++) {
int p = price[i];
// 正序遍历容量，支持重复选择
for (int j = p; j <= n; j++) {
dp[j] += dp[j - p];
}
}
System.out.println(dp[n]);
}
}
2022
解题思路(带数量约束的01 背包计数模型)
本题要求将整数 2022 拆分为 恰好 10 个互不相同的正整数 之和，求不同的拆分方案数（顺序无关）。
这本质上是一个 带数量限制的 01 背包计数问题。
问题转化：从“拆分”到“选数”
我们可以把问题理解为：
- 有物品
1, 2, 3, ..., 2022（每个正整数最多选一次） - 每个物品的“重量”等于其数值
- 要求 恰好选择 10 个物品，且总重量为 2022
- 求方案总数
✅ 这正是 01 背包的扩展：在标准“容量”维度基础上，新增“物品个数”维度。
三维状态定义（便于理解）
设 dp[i][j][k] 表示：
- 考虑前
i个正整数（即数字1到i） - 总和为
j - 恰好选择了
k个数 - 的方案数目
状态转移方程为：
dp[i][j][k] = dp[i-1][j][k] // 不选第 i 个数
+ dp[i-1][j - i][k - 1] // 选第 i 个数（需 j >= i 且 k >= 1）
初始条件：
dp[0][0][0] = 1- 其余为 0
二维滚动数组优化（实际实现）
观察转移方程可知：dp[i][...][...] 只依赖于 dp[i-1][...][...]，因此可以省略第一维，使用滚动数组。
定义优化后的状态：
dp[j][k]：当前已考虑若干数字后，总和为 j、恰好选了 k 个不同正整数 的方案数
注意：为了防止同一个数字被重复使用，必须 倒序遍历 j 和 k（标准 01 背包技巧）。
💡 注意：这里
j是总和（容量），k是数量，与最终目标dp[2022][10]对应。
状态转移与遍历顺序
对每个数字 i（从 1 到 2022）：
- 若选择
i，则从状态dp[j - i][k - 1]转移而来 - 转移式：
dp[j][k] += dp[j - i[k - 1]
为防止同一个数字被重复使用（01 背包特性），必须 倒序遍历 j 和 k：
- 外层：枚举物品
i - 中层：倒序遍历总和
j（从 2022 到 x） - 内层：顺序倒序都可以
✅ 倒序保证
dp[j - i][k - 1]来自上一轮（未包含当前i）的状态，避免重复选择。
初始化
dp[0][0] = 1：总和为 0、选 0 个数，有 1 种方案（空集）- 其余初始化为 0
最终答案为 dp[2022][10]。
参考代码
public class Main {
public static void main(String[] args) {
int sum = 2022;
int cnt = 10;
// dp[j][k]: 和为 j，选了 k 个不同正整数的方案数
long[][] dp = new long[sum + 1][cnt + 1];
dp[0][0] = 1; // 初始状态：和为 0，选 0 个数，有一种方案
// 枚举每个可能的正整数 i（物品）
for (int i = 1; i <= sum; i++) {
// 倒序遍历和 j，防止重复使用 i
for (int j = sum; j >= i; j--) {
// k的顺序无所谓
for (int k = cnt; k >= 1; k--) {
dp[j][k] += dp[j - i][k - 1];
}
}
}
System.out.println(dp[sum][cnt]);
}
}
选数异或
核心思想：01 背包的“异或”变形
这道题本质上是一个 动态规划问题，并且是经典的 01 背包模型的变种：
| 传统 01 背包 | 本题（异或背包） |
|---|---|
| 每个物品选或不选 | 每个数字选或不选 |
状态：总和为 j |
状态：异或值为 j |
转移：dp[j] += dp[j - w] |
转移：dp[j ^ a] += dp[j] |
目标：求和等于 W |
目标：异或等于 x |
✅ 共同点：每个元素只有“选”或“不选”两种选择，统计满足条件的方案数。
❗ 不同点：运算从“加法”变为“异或”，状态转移方式需调整。
动态规划设计
dp 数组定义
dp[j] 表示：当前已处理若干数字后，异或值恰好为 j 的子序列个数。
- 状态范围：由于题目保证
nums[i] ≤ 63，而异或结果最大不会超过63（即2^6 - 1），所以只需开64个状态。 - 初始化：
dp[0] = 1，表示空子序列异或值为 0，有 1 种方案。
状态转移逻辑
对于当前数字 nums[i]，我们考虑：
- 不选它：所有已有状态保持不变（
dp数组已保留） - 选它：对于每一个已有异或值
j，会新增一个异或值为j ^ nums[i]的子序列
因此转移方程为：
newDp[j ^ nums[i]] += oldDp[j]
⚠️ 注意：必须基于上一轮的完整状态进行转移，否则会重复计算。
所以每次循环前，先用oldDp = dp.clone()保存旧状态。
3. 为什么不能像普通背包那样倒序？
在加法背包中，j - w < j，倒序可避免覆盖。
但在异或中，j ^ nums[i] 可能大于、小于或等于 j，没有单调性，无法通过遍历顺序隔离新旧状态。
✅ 因此必须使用 临时数组（或二维 DP） 来保证正确性。
参考代码（Java）
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
final int MOD = 998244353;
final int MAX_XOR = 64; // 因为题目中 a[i] ≤ 63，异或结果最大为 63（2^6 - 1）
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int x = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
// dp[j] 表示当前异或值为 j 的子序列个数
long[] dp = new long[MAX_XOR];
dp[0] = 1; // 空子序列：异或值为 0，有 1 种方案
// 遍历每个数字（每个物品选或不选）
for (int i = 0; i < n; i++) {
// 保存上一轮的状态，防止状态覆盖
long[] oldDp = dp.clone();
// 枚举所有可能的异或值状态 j
for (int j = 0; j < MAX_XOR; j++) {
if (oldDp[j] != 0) {
int newXor = j ^ nums[i]; // 选择当前数字后的新异或值
dp[newXor] = (dp[newXor] + oldDp[j]) % MOD;
}
}
}
System.out.println(dp[x]);
}
}
