问题描述
小蓝有一个长度为 N 的数组 A =「Ao,A1,…,A~-1]。现在小蓝想要从 A 对应的数组下标所构成的集合I =0,1,2,… N-1 中找出一个子集 民1,那么 民」在I中的补集为Rz。记S=∑reR 4,S2=∑rERA,,我们要求S、和 S,均为偶数,请问在这种情况下共有多少种不同的 R,。当 民或 R,为空集时我们将 S.或 S₂视为 0。
输入格式
第一行一个整数 工,表示有 工 组数据。
接下来输入 工 组数据,每组数据包含两行:第一行一个整数 N表示数组 4 的长度;第二行输入 N 个整数从左至右依次为Ao,A1,……AN-1,相邻元素之间用空格分隔。
输出格式
对于每组数据,输出一行,包含一个整数表示答案,答案可能会很大,你需要将答案对 1000000007 进行取模后输出
样例说明
对于第一组数据,答案为 4。(注意:大括号内的数字表示元素在数组中的下标。)
R=0,Rz=1;此时S=Ao=6为偶数,Sz=A1=6为偶数。
R=1,Rz=0;此时S=A1=6为偶数,Sz=4o=6为偶数。
R=0,1,Rz= ;此时S= Ao+ A」= 12 为偶数S,-0为偶数。
R1=,Rz=0,1;此时S1=0为偶数,Sz=Ao+A1=12 为偶数。
对于第二组数据,无论怎么选择,都不满足条件,所以答案为 0
评测用例规模与约定
对于
% 的评测用例,1<N<10.
对于
% 的评测用例,1<N<102
对于100%的评测用例,1<T<10,1<N<10,0<A<109
运行限制
语言
C++
Java
Python3
PyPy3
Go
JavaScript
最大运行时间1S1S2s
3s
3s
3s
3s
最大运行内存
512M
512M
512M
512M
512M
512M
512M
当奇数的个数为奇数时,和为奇数,不满足题意
当奇数的个数为偶数时,和为偶数,满足题意。此时种数为2的偶数个数的次方 x 2的奇数个数的次方
// 参考@张峻齐
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int T = scanner.nextInt();int[] ans = new int[T];for (int i = 0; i < T; ++i) {int N = scanner.nextInt();int evenCount = 0, oddCount = 0;for (int j = 0; j < N; ++j) {int e = scanner.nextInt();if (e % 2 == 0) ++evenCount;else ++oddCount;}if (oddCount % 2 == 0)ans[i] = (int) (Math.pow(2, evenCount) * Math.pow(2, oddCount == 0 ? 0 : oddCount - 1) % 1000000007);else ans[i] = 0;}scanner.close();for (int e : ans) System.out.println(e);}
}
近日总结:背过的东西直接就忘记了......