打卡信奥刷题（2165）用C++实现信奥 P12325 [蓝桥杯 2023 省 Java B] 数组分割

rogeliu

913人浏览 · 2025-10-05 11:02:37

rogeliu · 2025-10-05 11:02:37 发布

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

题目描述

小蓝有一个长度为 $N$ 的数组 $A = [A_0, A_1, ..., A_{N-1}]$ 。现在小蓝想要从 $A$ 对应的数组下标所构成的集合 $I = {0, 1, 2, ..., N - 1}$ 中找出一个子集 $R_1$ ，那么 $R_1$ 在 $I$ 中的补集为 $R_2$ 。记 $S1=∑r∈R1ArS_1 = \displaystyle \sum_{r \in R_1} A_r$ ， $S2=∑r∈R2ArS_2 = \displaystyle \sum_{r \in R_2} A_r$ ，我们要求 $S_1$ 和 $S_2$ 均为偶数，请问在这种情况下共有多少种不同的 $R_1$ 。当 $R_1$ 或 $R_2$ 为空集时我们将 $S_1$ 或 $S_2$ 视为 $0$ 。

输入格式

第一行一个整数 $T$ ，表示有 $T$ 组数据。

接下来输入 $T$ 组数据，每组数据包含两行：第一行一个整数 $N$ ，表示数组 $A$ 的长度；第二行输入 $N$ 个整数从左至右依次为 $A_0, A_1, ..., A_{N-1}$ ，相邻元素之间用空格分隔。

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

4
0

说明/提示

样例说明

对于第一组数据，答案为 $4$ 。（注意：大括号内的数字表示元素在数组中的下标。）

$R_1 = \{0\}, R_2 = \{1\}$ ；此时 $S_1 = A_0 = 6$ 为偶数， $S_2 = A_1 = 6$ 为偶数。
$R_1 = \{1\}, R_2 = \{0\}$ ；此时 $S_1 = A_1 = 6$ 为偶数， $S_2 = A_0 = 6$ 为偶数。
${}R_1 = \{0, 1\}, R_2 = \{\}$ ；此时 $S_1 = A_0 + A_1 = 12$ 为偶数， $S_2 = 0$ 为偶数。
$R_1 = \{\}, R_2 = \{0, 1\}$ ；此时 $S_1 = 0$ 为偶数， $S_2 = A_0 + A_1 = 12$ 为偶数。

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

评测用例规模与约定

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

C++实现

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
long long powss(long long base, int exps, int mod) {
	long long result = 1;
	while (exps > 0) {
		if (exps % 2 == 1) {
			result = (result * base) % mod;
		}
		base = (base * base) % mod;
		exps /= 2;
	}
	return result;
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		int N;
		cin >> N;
		vector<int> A(N);
		int c1 = 0;
		for (int i = 0; i < N; ++i) {
			cin >> A[i];
			if (A[i] % 2 != 0) {
				c1++;
			}
		}
		if (c1 % 2 != 0) {
			cout << 0 << endl;
		} else {
			if (c1 == 0) {
				cout << powss(2, N, MOD) << endl;
			} else {
				cout << powss(2, N - 1, MOD) << endl;
			}
		}
	}
	return 0;
}