```cpp #include<bits/stdc++.h> using namespace std; const int N=1e3+10; const int mod=1000000007; int a[N],dp[N][N]; int main(){ int t; cin >> t; while(t--){ int n;cin >> n; long long sum=0; for(int i =1;i<=n;i++){ cin >> a[i]; sum+=a[i]; } if(sum%2==1){ cout << 0<<endl; continue; } memset(dp,0,sizeof(dp)); dp[0][0]=1; dp[0][1]=0; for(int i =1;i<=n;i++){ if(a[i]%2==0){ dp[i][0]+=dp[i-1][0]*2%mod; dp[i][1]+=dp[i-1][1]*2%mod; } else{ dp[i][1]+=dp[i-1][0]+dp[i-1][1]; dp[i][0]+=dp[i-1][1]+dp[i-1][0]; } dp[i][0]%=mod; dp[i][1]%=mod; } cout << dp[n][0] <<endl; } return 0; } ```

数组分割 前置知识 - 二项式定理 - 取模运算 ```c++ (a + b) % p = (a % p + b % p) % p (a - b) % p = (a % p - b % p + p) % p (a * b) % p = (a % p * b % p) % p a ^ b % p = ((a % p) ^ b) % p ``` 题目思路 - $n$ 个数要分成两个集合 $S_1$ 和 $S_2$ 并且两个集合各自的元素之和都为偶数，我们需要先思考如何凑出和为偶数的情况： - 偶数个偶数的和为偶数 - 偶数个奇数的和为偶数 所以我们在把 $n$ 个数划分为两个集合，里面的元素必须满足上面两种情况之一，我们需要先统计 $n$ 个数中奇数和偶数的数量，如果奇数个数为奇数个一定无法满足两个集合元素之和为偶数的条件。 - 知道集合中的元素必须要满足什么性质之后我们需要计算出满足条件的情况数量，设偶数个数为 $a$，奇数个数为 $b$： - 偶数个偶数的情况数量(设情况数量为 $S_1$)： $S_1=C_{a}^0+C_{a}^1+...+C_{a}^a = 2^a$ 为什么组和数最后和为 $2 ^ a$，我们需要借助二项式定理 我们假设 $a = 1$ 和 $b = 1$ 可得到 $(1 + 1)^n = C_{n}^0+C_{n}^1+...+C_{n}^n$ - 偶数个奇数的和为偶数(设情况数量为 $S_2$) ​ $S_2=C_{b}^0+C_{b}^2+...+C_{b}^b = 2^{b-1}$ （奇数必须两个两个的取） ​ 为什么会有这样一个等式，我们还是要借助二项式定理 ​ 假设 $a = 1$ 和 $b = 1$ 可得到 $(1 + 1)^n = C_{n}^0+C_{n}^1+...+C_{n}^n\ (1)$ ​ 假设 $a=1$ ，$b=-1$ 并且 $n$ 为偶数可得到 $0 = C_{n}^0-C_{n}^1+C_{n}^2-C_{n}^3...+C_{n}^n\ (2)$ ​ 我们将 $(1) + (2)$ 可得到 $C_{n}^0+C_{n}^2+...+C_{n}^2 = 2^{n-1}$ - 最后我们再把子集个数分成以下三种情况： - 奇数个奇数，可能的情况个数为 $0$ - 奇数个数为 $0$，可能的情况个数为 $2 ^ a$ - 奇数个数为偶数个并且不等于 $0$，可能的情况个数为 $2^{a + b - 1}$ - 本题 $n \leq 1000$ 且不超过 $10$ 组输入，所以即使不用快速幂也不会超时,最后不要忘了在运算过程中加上取模。 代码 ```c++ #include<bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; int main() { int t; cin >> t; while(t--) { int n; cin >> n; int a = 0,b = 0; for(int i = 1;i <= n;i++) { int t; cin >> t; if(t % 2 == 0) { a++; } else { b++; } } long long res = 1; if(b % 2 != 0) {//奇数个奇数 cout << 0 << endl; } else { if(b == 0) {//奇数个数为0 for(int i = 1;i <= a;i++) { res = ((res % mod) * (2 % mod)) % mod; } } else { for(int i = 1;i <= a + b - 1;i++) { res = ((res % mod) * (2 % mod)) % mod; } } cout << res << endl; } } } ``` ```Java import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int mod = 1000000007; int t = scanner.nextInt(); while (t-- > 0) { int n = scanner.nextInt(); int a = 0, b = 0; for (int i = 1; i <= n; i++) { int num = scanner.nextInt(); if (num % 2 == 0) { a++; } else { b++; } } long res = 1; if (b % 2 != 0) { // 奇数个奇数 System.out.println(0); } else { if (b == 0) { // 奇数个数为0 for (int i = 1; i <= a; i++) { res = ((res % mod) * (2 % mod)) % mod; } } else { for (int i = 1; i <= a + b - 1; i++) { res = ((res % mod) * (2 % mod)) % mod; } } System.out.println(res); } } } } ```

``` import java.util.*; public class Main{ static Scanner sc = new Scanner(System.in); static int MOD = (int)(1e9+7); public static void main(String[] args) { int T = sc.nextInt(); while(T-- > 0) { solve(); } } static void solve() { int n = sc.nextInt(); int E = 0,O = 0; for(int i = 1;i<= n;i++) { int x = sc.nextInt(); if(x % 2 == 0) E++; else O++; } if(O % 2 !=0) System.out.println(0); else System.out.println(myPow(E)*myPow(O-1)%MOD); } static long myPow(long k) { long ans = 1; long base = 2; while(k>0) { if(k % 2 == 1) ans = ans % MOD * base % MOD; base = base % MOD * base % MOD; k /= 2; } return ans % MOD; } } ```

```python t = int(input()) for _ in range(t): n = int(input()) l = list(map(int,input().split())) a = len(list(filter(lambda x: x%2==0,l))) b = n - a if b % 2 != 0: print(0) continue else: print(pow(2,a+max(1,b)-1,1000000007)) ```