在动态规划中理解奇数情况的关键点在于考虑加入一个奇数对奇偶性的影响。
初始状态
我们先建立一个基础。动态规划表 dp[i][0] 被用来存储考虑前 i 个数字后,能够形成的所有偶数和的组合数。同理,dp[i][1] 被用来存储考虑前 i 个数字后,能够形成的所有奇数和的组合数。初始状态下,我们有 dp[0][0] = 1 和 dp[0][1] = 0,因为没有任何数字时,我们只有一个和为0的组合(一个空集,它是偶数)。
状态转移
接下来,我们加入数字 a[i],我们要更新 dp[i][0] 和 dp[i][1]。如何更新这些值,取决于 a[i] 是奇数还是偶数。
当 a[i] 是偶数时
当我们遇到一个偶数,这个数可以加入到任何现有的组合中而不改变那个组合的奇偶性。因此,对于每个现有的偶数和组合,我们可以选择包括这个新的偶数,使得组合仍然是偶数,或者选择不包括它。这意味着每一种可能性都可以翻倍。这就是为什么我们用 dp[i-1][0] * 2 和 dp[i-1][1] * 2 来更新。
当 a[i] 是奇数时
奇数的情况稍微复杂一些。加入一个奇数会改变组合的奇偶性。我们可以这样思考:
对于所有以前的偶数和组合(dp[i-1][0]),如果我们加上这个奇数,这些组合现在变成了奇数和。
对于所有以前的奇数和组合(dp[i-1][1]),如果我们加上这个奇数,这些组合现在变成了偶数和。
所以,现在的偶数和组合可以由两个来源组成:
所有之前的偶数和组合,但不包括当前的奇数(维持偶数和)。
所有之前的奇数和组合,现在加上当前的奇数(从奇数变成偶数)。
这就是为什么我们用 dp[i-1][0] + dp[i-1][1] 来更新 dp[i][0]。
同理,现在的奇数和组合也有两个来源:
所有之前的奇数和组合,但不包括当前的奇数(维持奇数和)。
所有之前的偶数和组合,现在加上当前的奇数(从偶数变成奇数)。
这也是为什么 dp[i][1] 用相同的公式 dp[i-1][0] + dp[i-1][1] 来更新。
换句话说,当加入一个奇数时,之前的偶数和变成新的奇数和,之前的奇数和变成新的偶数和。因此,不论之前是偶数和还是奇数和,新的组合都包含了所有之前的组合数量。
import java.util.*;
public class Main {
static final int N = 1010; // 定义数组的最大长度
static final int MOD = 1000000007; // 定义模数,用于处理大数溢出
static int[] a = new int[N]; // 输入数组,用于存储元素
static int[][] dp = new int[N][2]; // DP数组,dp[i][j]将存储使用前i个数字,和为j的子集数量
public static void main(String[] args) {
Scanner sca = new Scanner(System.in);
int T = sca.nextInt(); // 读取测试用例的数量
while (T-- > 0) {
int n = sca.nextInt(); // 读取当前测试用例中元素的数量
long sum = 0;
for (int i = 1; i <= n; i++) {
a[i] = sca.nextInt(); // 存储每个元素到数组中
sum += a[i];
Arrays.fill(dp[i], 0); // 初始化当前元素对应的DP数组
}
if((sum & 1) == 1){
System.out.println(0);
continue;
}
dp[0][0] = 1; // 基础情况:使用0个元素构成和为0的子集(空集)的方式有1种
for (int i = 1; i <= n; i++) {
if ((a[i] & 1) == 0) { // 如果当前元素是偶数
// 如果a[i]是偶数,我们可以选择包含它或不包含它而不影响子集和的奇偶性
dp[i][0] = (dp[i - 1][0] * 2) % MOD; // 更新偶数和子集的数量
dp[i][1] = (dp[i - 1][1] * 2) % MOD; // 更新奇数和子集的数量
} else { // 如果当前元素是奇数
// 如果a[i]是奇数,加上它将翻转子集和的奇偶性
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; // 更新偶数和子集的数量
dp[i][1] = (dp[i - 1][1] + dp[i - 1][0]) % MOD; // 更新奇数和子集的数量
}
}
System.out.println(dp[n][0]); // 输出所有元素都考虑之后,形成偶数和的组合数量
}
}
}