辽宁建设工程质量监督站网站,小型视频网站建设,动易网站后台密码破解,阜新网站优化题目链接
数组分割
个人思路
两个数组都需要和为偶数#xff0c;那么就去思考一个数组如何才能和是偶数呢#xff1f;#xff1f;
数组里肯定要么是奇数要么是偶数#xff0c;偶数无论有多少个#xff0c;都不会改变一个数组的奇偶性。但是奇数个奇数的和还是奇数那么就去思考一个数组如何才能和是偶数呢
数组里肯定要么是奇数要么是偶数偶数无论有多少个都不会改变一个数组的奇偶性。但是奇数个奇数的和还是奇数偶数个奇数的和就会是偶数这个应该就不用证明了吧。
那么这个问题就被转换为求数组中奇数的个数
当我们遍历完数组后获取到数组中奇数与偶数的个数。如果奇数的数量为奇数那么我们无论怎么去分都无法将奇数个奇数分成两边都是偶数个奇数即奇数无法拆成两个偶数这种情况下答案的个数就为 0。
那么如果为偶数(n)个奇数那么我只需要每次从奇数中选择024… n个奇数作为其中一个集合的数剩下的交给另外一个集合这就是数学中的组合问题用公式表示就是 C n 0 C n 2 … C n n 2 n − 1 C_{n}^{0}C_{n}^{2}\ldots C_{n}^{n}2^{n-1} Cn0Cn2…Cnn2n−1 对于偶数的话我们就没有那么多限制直接从中选取0123… n个偶数随意组合公式就是 C n 0 C n 1 C n 2 … C n n 2 n C _{n}^{0}C_{n}^{1}C_{n}^{2}\ldots C_{n}^{n}2^{n} Cn0Cn1Cn2…Cnn2n 不过这边存在一个问题如果奇数的个数为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;
}
