This is because the two vector sets (in Base 2) are linearly convertible and there exist a reverse mapping as well.

In such case, the underlying basis will remain same for both the vector space as no independent vectors are getting dissolved.

Consider that, poss[a][0] is the number of ways to select even number of elements equal to a, and poss[a][1] is the number of odd so far. This is without considering the current input. Now, let's say we encounter a new 'a', then we can re-calculate our poss values.

poss[a][0] = (earlier number of possibilities, ignoring current 'a') + (earlier number of poss of selecting odd elements and adding current 'a' into them to mqke overall even).

Thus, poss[a][0] = poss[a][0] + poss[a][1]

Similarly, poss[a][1] is updated.

Hey thanks for your reply! and yes I do understand how the second solution works.

How to solve Div2E/Div1B recursively? or how to find the length of the first block?

Hi can you please provide a proof for your claim? Thanks!

What is the proof for Div1B?

Let's say the answer to the problem is not $$$0$$$. Then how to prove that in the case $$$(3)$$$ while choosing any of the $$$a_{i-1}$$$ or $$$a_{i+1}$$$ will always lead to the solution in the end rather than ending up in a contradiction later on.

Also check SRM 518 1000 for how to use FWT. http://apps.topcoder.com/wiki/display/tc/SRM+518

This link is not working anymore, if possible someone can provide a working link?

Div2 B can also be solved with bitsets
Accepted Solution : 80020525

Try using fast i/o :-

ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

Yes, they are identical.

Check out if you have used "long long int" instead of "int". I also got WA at test case 4, and this helped me :)

Can someone explain Div1 E?

Any updates regarding how to solve this?

Hey can someone tell me where I am wrong...this code is giving wrong answer on 17th test case... Problem B

http://codeforces.me/contest/913/submission/34023515