Subarrays with Even Product
National Olympiad — National round (2025 season)
Submission name: even.cpp
Problem summary
Count all nonempty contiguous subarrays whose product is even. Array values are nonnegative, so a zero also makes a product even.
Input
N, then N nonnegative integers.
Output
The number of subarrays with even product.
Constraints
1 ≤ N ≤ 3000000; 0 ≤ value < 600000; memory limit 3 MB.
Worked example
An independently prepared example for this explanation.
Input
5 1 2 3 4 5
Output
12
Solution analysis
- A product is even exactly when at least one factor is even. Avoid multiplying the values: only their parity matters.
- Process right endpoints in one pass. Keep the position of the latest even value, using one-based positions and zero when none has appeared. For a subarray ending at i, its starting point may be any position from 1 through that latest even position.
- For 1,2,3,4,5, the contributions by right endpoint are 0,2,2,4,4. Their sum is 12. This streaming method also handles zero without special cases beyond the even test.
Why it works
For a fixed right endpoint, a subarray contains an even factor exactly when it starts at or before the most recent even position. There are exactly lastEven such starts. Summing over right endpoints counts every valid subarray once.
Watch out. Zero is even. Use long long for the answer because the number of subarrays can be about 4.5 trillion.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
long long lastEven = 0, answer = 0;
for (int position = 1; position <= n; position++) {
int value;
cin >> value;
if (value % 2 == 0) {
lastEven = position;
}
// Every start at or before the latest even position gives an even product.
answer += lastEven;
}
cout << answer << '\n';
}