PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: likhon5
Tester & Editorialist: iceknight1093
DIFFICULTY:
1612
PREREQUISITES:
Basic combinatorics
PROBLEM:
You’re given an array A. Find the number of non-empty subsets of indices whose removal results in every subarray having even sum.
EXPLANATION:
Suppose we removed some indices, and the array satisfies the given condition, i.e, \displaystyle\sum_{k=i}^j A_k is even, for each 1 \leq i \leq j \leq |A|.
Then, in particular this holds for i = j, which means every element must itself be even.
Of course, if every element is even then every subarray sum is also even; so we’ve reduced our problem to counting the number of ways of removing indices such that all remaining elements are even.
That’s not too hard:
- First, all odd elements must be removed.
- Suppose this leaves K even elements. We can then choose any subset of them to remove, for 2^K possible ways.
There’s one edge case: since the statement asks for non-empty subsets, if K = N (i.e all elements of the original array are even), the answer is 2^N - 1; since we can’t choose the empty subset.
Since K \leq N, computing 2^K can be done by just repeated multiplication using a loop.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
#define endl '\n'
#define filein freopen("input20.in","r",stdin)
#define fileout freopen("output20.out","w",stdout)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mx=2e5+9;
const int mod=1e9+7;
int main()
{
fast;
int t; cin>>t;
assert(t<=10000);
int total=0;
while(t--)
{
int n; cin>>n;
total+=n;
int odd=0,even=0;
for(int i=0;i<n;i++)
{
int x; cin>>x;
assert(x>=0 and x<=200000);
if(x%2) odd++;
else even++;
}
long long cnt=1;
for(int i=1;i<=even;i++) cnt=(cnt*2)%mod;
if(odd) cout<<cnt<<endl;
else cout<<cnt-1<<endl;
}
assert(total<=200000);
}
Editorialist's code (Python)
mod = 10**9 + 7
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
evens = 0
for x in a: evens += (x+1)%2
ans = pow(2, evens, mod)
if evens == n: ans -= 1
print(ans%mod)