阿狗工具

题目描述

小红拿到了一个长度为n的数组。她希望把一些数（不少于2个数）染红，满足任意两个染红的数之和都是偶数。小红想知道，一共有多少种不同的染色方案？答案对取模。我们认为，对两个方案，只要存在某个数的染色情况不同，则认为是两种不同的方案。

输入描述

第一行输入一个正整数n，代表数组的长度。
第二行输入n个正整数，代表小红拿到的数组。
数据范围：

输出描述

输出一个整数，代表染色方案对取模。

示例1

输入

5
1 2 5 2 8

输出

5

说明

共有以下5种方案：
{1, 5}、{2，2}、{2, 8}、{2, 8}、{2, 2, 8}，其中{2, 8}有两种方案
第一种是染红数组第二、第五个数，第二种是染红数组第四、第五个数。

代码

//Node 模式
let readlineSync = require('readline-sync');
readlineSync.setDefaultOptions({ prompt: '' });
let readline = readlineSync.prompt;

const MOD = 1e9 + 7;
let n = readline();
let arr = readline().split(" ");
let nums = new Array(n);
for(let i = 0; i < n; i++) {
    nums[i] = parseInt(arr[i]);
}
let oddCount = 0;
let evenCount = 0;
for(const num of nums) {
    if(num % 2 === 0) {
        evenCount++;
    } else {
        oddCount++;
    }
}
let res1 = 1;
//C(0,n)+C(1,n)+C(2,n)+...C(n,n)=2^n
for(let i = 0; i < evenCount; i++) {
    res1 = (res1 * 2) % MOD;
}
res1 = (res1 + MOD - evenCount - 1) % MOD;
let res2 = 1;
for(let i = 0; i < oddCount; i++) {
    res2 = (res2 * 2) % MOD;
}
res2 = (res2 + MOD - oddCount - 1) % MOD;
console.log((res1 + res2) % MOD);