【蓝桥备赛】数组分割——组合数学？

题目链接

数组分割

个人思路

两个数组都需要和为偶数，那么就去思考一个数组如何才能和是偶数呢？？

数组里肯定要么是奇数要么是偶数，偶数无论有多少个，都不会改变一个数组的奇偶性。但是奇数个奇数的和还是奇数，偶数个奇数的和就会是偶数（这个应该就不用证明了吧）。

那么这个问题就被转换为，求数组中奇数的个数！

当我们遍历完数组后，获取到数组中奇数与偶数的个数。如果奇数的数量为奇数，那么我们无论怎么去分，都无法将奇数个奇数分成两边都是偶数个奇数（即奇数无法拆成两个偶数），这种情况下，答案的个数就为 0。

那么如果为偶数(n)个奇数，那么我只需要每次从奇数中选择0，2，4，… ，n个奇数作为其中一个集合的数，剩下的交给另外一个集合，这就是数学中的组合问题，用公式表示就是：
$$C_n^0+C_n^2+\dots +C_n^n=2^{n-1}$$
对于偶数的话，我们就没有那么多限制，直接从中选取0，1，2，3，… ，n个偶数，随意组合：公式就是
$$C_n^0+C_n^1+C_n^2+\dots +C_n^n=2^n$$
不过这边存在一个问题，如果奇数的个数为0个，那么就不存在 n-1的情况，所以需要特别处理。
另外在计算这些的过程中，可能会出现数过大的情况需要取模运算，我直接选择了快速幂。

参考代码

Java

import java.util.Scanner;public class Main {static int n;static long[] arr;static long res;static long MOD = 1000000007;static long ksm(long a, long b) {long cnt = 1;while (b > 0) {if ((b & 1) == 1) {cnt = cnt * a % MOD;}a = a * a % MOD;b >>= 1;}return cnt;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int t = sc.nextInt();while (t-- > 0) {n = sc.nextInt();arr = new long[n + 1];// odd 奇数个数int odd = 0;for(int i = 1; i <= n; ++i) {arr[i] = sc.nextLong();if(arr[i] % 2 == 1) {++odd;}}// 一个数组的和是否是偶数，取决于奇数的个数一定要是偶数个,剩余偶数的组合随意int even = n - odd;// 如果奇数的个数为奇数个,那么就无法组成和为偶数的数组if (odd % 2 == 1) {System.out.println(0);continue;}// 对于每一个奇数情况,都相当于从odd个中选i个(组合公式),但是i必须是偶数个// 选择完奇数后,剩余偶数从选0个到全选// 也就是在求 2^(odd - 1) * 2^even// 啊！！！震惊// 不过如果奇数为 0 个,此处就不用减去1了if(odd == 0) {res = ksm(2, even);} else {res = ksm(2, even) * ksm(2, odd - 1) % MOD;}System.out.println(res);}}
}

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 3;
const ll MOD = 1000000007;int n;
ll arr[N];
ll res;ll ksm(ll a, ll b) {ll cnt = 1;while (b > 0) {if (b & 1) {cnt = (cnt * a) % MOD;}a = (a * a) % MOD;b >>= 1;}return cnt;
}int main() {int t;cin >> t;while (t-- > 0) {cin >> n;int odd = 0;for (int i = 1; i <= n; ++i) {cin >> arr[i];if (arr[i] % 2 == 1) {++odd;}}int even = n - odd;if (odd % 2 == 1) {cout << 0 << endl;continue;}if (odd == 0) {res = ksm(2, even);} else {res = (ksm(2, even) * ksm(2, odd - 1)) % MOD;}cout << res << "\n";}return 0;
}