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

· · 题解

一道有意思的题。

问题描述

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

解题思路

奇偶分析：

数组中的元素分为奇数和偶数，只有当奇数的 数量为偶数 时，整个数组的和才为偶数，此时可能存在符合条件的子集。若 奇数数量为奇数，直接返回 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; }



[记录详情](https://www.luogu.com.cn/record/215036796)