自动搬运

查看原文

来自洛谷，原作者为

	wf2025 主页：https://www.luogu.me/paste/emdgqxce

搬运于2025-08-24 23:14:38，当前版本为作者最后更新于2025-04-25 20:50:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道有意思的题。

问题描述

给定一个数组，将元素重新划分为两个互补的子集，要求两个子集中的元素和均为偶数。求满足条件的不同划分方式有多少种。

解题思路

奇偶分析：

数组中的元素分为奇数和偶数，只有当奇数的 数量为偶数 时，整个数组的和才为偶数，此时可能存在符合条件的子集。若 奇数数量为奇数，直接返回 $0$，无法满足条件。

组合计算：

令 $n$ 为数组长度。

1. 若数组全为偶数，所有子集均满足条件，数目为 $2^{n}$。
2. 若奇数数量为偶数且不为 $0$，符合条件的子集数目为 $2^{n-1}$。
   计算答案时一定取模。

code

#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;
}

记录详情