yukicoder no. 803 Very Limited Xor Subset

https://yukicoder.me/problems/no/803

Once we realize this problem is related to a system of linear equations, this problem has been almost solved. All we have to do is to find the number of solutions of the given linear system.

Let u be a solution of Ax=b and v be a solution of Ax=0. Then u+v is also a solution. Actually, any solution can be written as u+v where v is a solution of Ax=0. So, the number of solutions of Ax=0 is equal to the number of solutions of Ax=b unless Ax=b has no solutions. The set of solutions of Ax=0 is called the kernel, denoted by ker A. In fact, ker A forms a vector space. Thus, if we know the dimension of ker A, we can find out the number of elements contained in ker A. The dimension of ker A can be computed by the rank–nullity theorem (also known as the dimension theorem.) This theorem says dim ker A + dim im A = N. So if we have the rank of A (=dim im A), we can solve this problem immediately.