#P12325. [蓝桥杯 2023 省 Java B] 数组分割

[蓝桥杯 2023 省 Java B] 数组分割

题目描述

小蓝有一个长度为 NN 的数组 A=[A0,A1,...,AN1]A = [A_0, A_1, ..., A_{N-1}]。现在小蓝想要从 AA 对应的数组下标所构成的集合 I=0,1,2,...,N1I = {0, 1, 2, ..., N - 1} 中找出一个子集 R1R_1,那么 R1R_1II 中的补集为 R2R_2。记 S1=rR1ArS_1 = \displaystyle \sum_{r \in R_1} A_rS2=rR2ArS_2 = \displaystyle \sum_{r \in R_2} A_r,我们要求 S1S_1S2S_2 均为偶数,请问在这种情况下共有多少种不同的 R1R_1。当 R1R_1R2R_2 为空集时我们将 S1S_1S2S_2 视为 00

输入格式

第一行一个整数 TT,表示有 TT 组数据。

接下来输入 TT 组数据,每组数据包含两行:第一行一个整数 NN,表示数组 AA 的长度;第二行输入 NN 个整数从左至右依次为 A0,A1,...,AN1A_0, A_1, ..., A_{N-1},相邻元素之间用空格分隔。

输出格式

对于每组数据,输出一行,包含一个整数表示答案,答案可能会很大,你需要将答案对 10000000071\,000\,000\,007 进行取模后输出。

2
2
6 6
2
1 6
4
0

提示

样例说明

对于第一组数据,答案为 44。(注意:大括号内的数字表示元素在数组中的下标。)

  • R1={0},R2={1}R_1 = \{0\}, R_2 = \{1\};此时 S1=A0=6S_1 = A_0 = 6 为偶数,S2=A1=6S_2 = A_1 = 6 为偶数。
  • R1={1},R2={0}R_1 = \{1\}, R_2 = \{0\};此时 S1=A1=6S_1 = A_1 = 6 为偶数,S2=A0=6S_2 = A_0 = 6 为偶数。
  • R1={0,1},R2={}R_1 = \{0, 1\}, R_2 = \{\};此时 S1=A0+A1=12S_1 = A_0 + A_1 = 12 为偶数,S2=0S_2 = 0 为偶数。
  • R1={},R2={0,1}R_1 = \{\}, R_2 = \{0, 1\};此时 S1=0S_1 = 0 为偶数,S2=A0+A1=12S_2 = A_0 + A_1 = 12 为偶数。

对于第二组数据,无论怎么选择,都不满足条件,所以答案为 00

评测用例规模与约定

  • 对于 20%20\% 的评测用例,1N101 \leq N \leq 10
  • 对于 40%40\% 的评测用例,1N1021 \leq N \leq 10^2
  • 对于 100%100\% 的评测用例,$1 \leq T \leq 10, 1 \leq N \leq 10^3, 0 \leq A_i \leq 10^9$。