Time limit : 2sec / Memory limit : 256MB
Score : 200 points
Problem Statement There are N bags of biscuits. The i-th bag contains Ai biscuits.
Takaki will select some of these bags and eat all of the biscuits inside. Here, it is also possible to select all or none of the bags.
He would like to select bags so that the total number of biscuits inside is congruent to P modulo 2. How many such ways to select bags there are?
Constraints 1≤N≤50 P=0 or 1 1≤Ai≤100 Input Input is given from Standard Input in the following format:
N P A1 A2 … AN Output Print the number of ways to select bags so that the total number of biscuits inside is congruent to P modulo 2.
Sample Input 1 2 0 1 3 Sample Output 1 2 There are two ways to select bags so that the total number of biscuits inside is congruent to 0 modulo 2:
Select neither bag. The total number of biscuits is 0. Select both bags. The total number of biscuits is 4. Sample Input 2 1 1 50 Sample Output 2 0 Sample Input 3 3 0 1 1 1 Sample Output 3 4 Two bags are distinguished even if they contain the same number of biscuits.
Sample Input 4 45 1 17 55 85 55 74 20 90 67 40 70 39 89 91 50 16 24 14 43 24 66 25 9 89 71 41 16 53 13 61 15 85 72 62 67 42 26 36 66 4 87 59 91 4 25 26 Sample Output 4 17592186044416
题目大意：有一些背包，每个背包有一定数目的饼干，从中选若干个背包，使得总数模2等于给定的数。 解题思路：由于只可能是奇数或偶数，所以只要考虑一种情况就好了，比如考虑总数是奇数，那么设奇数有x个，偶数有y个，那么当 x≥1 时，可能的情况数是 (C1x+C2x+...+Cxx)/2×2y=2x−1×2y
#include<iostream> using namespace std; typedef long long LL; const int MAXN=105; int a[MAXN]; int n,p; int odd,even; int main() { while(cin>>n>>p) { odd=0; even=0; for(int i=1;i<=n;i++) { cin>>a[i]; if(a[i]&1) odd++; else even++; } LL num; if(odd==0) num=0; else { num=((LL)1<<(odd-1))*((LL)1<<even); } if(p&1) { cout<<num<<endl; }else { cout<<((LL)1<<n)-num<<endl; } } return 0; }