题目内容

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

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

题面描述

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

思路

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

cpp