题面描述

小塔拿到了一个长度为$n$的数组，他希望选择一些数（不少于$2$个）进行染红，满足任意两个染红的数之和都是偶数。小塔想知道一共有多少种不同的染色方案。方案被认为是不同的，如果存在某个数的染色情况不同。输入的第一行是一个正整数$n$，表示数组的长度；第二行是$n$个正整数$a_i$，表示数组的元素。输出一个整数，表示染色方案的总数，结果对$10^9 + 7$取模。

思路

显然如果有一个奇数和一个偶数被染色那么一定不符合要求，所以要么全选偶数要么全选奇数，分别统计偶数和奇数个数，如果数量$>=2$那么根据组合数推论可得方案数为$C(odd,2)+C(odd,3)+......+C(odd,odd)$等于$2^{odd}-1-odd$对于偶数同理,最后加起来即可

cpp

题目内容

小塔拿到了一个长度为$n$的数组。

他希望把一些数(不少于$2$个数)染红，满足任意两个染红的数之和都是偶数。

小塔想知道，一共有多少种不同的染色方案?答案对$10^9+7$取模。

我们认为，对于两个方案，只要存在某个数的染色情况不同，则认为是两种不同的方案。

输入描述

第一行输入一个正整数$n$，代表数组的长度。

第二行输入$n$个正整数$a_i$，代表小塔拿到的数组。

输出描述

输出一个整数，代表染色方案对$10^9+7$取模的值。

样例1

输入

5
1 2 5 2 8

输出

5

说明

共有以下5种方案:

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