### PROBLEM LINK:

**Author:** Hiroto Sekido

**Tester:** Anton Lunyov

**Editorialist:** Anton Lunyov

### DIFFICULTY:

HARD

### PREREQUISITES:

Determinant, Cauchy-Binet formula, Gauss-Jordan elimination, Bitwise operations

### PROBLEM:

Getting rid of the story line we have the following problem.

You are given **N × N** matrices **Q _{1}, Q_{2}, …, Q_{B}**.

For each

**a**and

**b**such that

**1 ≤ a < b ≤ B**we construct the matrix

**C**by the formula

_{a,b}**C**for

_{a,b}[i][j] = Sum[Q_{a}[i][k] * Q_{b}[j][k] : 1 ≤ k ≤ N]**1 ≤ i, j ≤ N**.

For each permutation

**p = {p[1], p[2], …, p[N]}**of integers from

**1**to

**N**, inclusive, we consider the sequence

**Tr(p) = {C**.

_{a,b}[i][p[i]] : 1 ≤ i ≤ N}Denote by

**CNT(a, b)**the number of permutations

**p**, for which the sequence

**Tr(p)**has at least one odd element.

We call the pair

**(a, b)**good if

**CNT(a, b)**is odd.

Now the task is to calculate the total number of good pairs.

### QUICK EXPLANATION:

In the case **N = 1** the answer is **M * (M − 1) / 2** where **M** be the number of odd values among **{Q _{a}[1][1] : 1 ≤ a ≤ B}**.

So let **N** be at least **2**.

Since permanent of the matrix coincides with its determinant modulo 2 (see here) then the pair **(a, b)** is good if and only if **det(D _{a,b}) mod 2 = 1**, where

**D**.

_{a,b}[i][j] = (C_{a,b}[i][j] + 1) mod 2Let’s add column composed of ones to each matrix **Q _{c}** and assume that each

**Q**is actually

_{c}**N × (N+1)**matrix having last column composed of ones. Then

**D**, where

_{a,b}= (Q_{a})^{T}* Q_{b}mod 2**A**is the matrix transpose to

^{T}**A**.

By Cauchy-Binet formula **det(D _{a,b}) mod 2 = Sum[det(Q_{a,c}) * det(Q_{b,c}) : 1 ≤ c ≤ N+1] mod 2**,

where

**Q**is the matrix obtained from

_{a,c}**Q**by deleting its

_{a}**c**-th column.

Introducing numbers **V _{a} = Sum[(det(Q_{a,c}) mod 2) * 2^{c-1} : 1 ≤ c ≤ N+1]** we can rewrite

**det(D**as

_{a,b}) mod 2**bitCount(V**, where

_{a}& V_{b}) mod 2**X & Y**is a bitwise “and” of the numbers

**X**and

**Y**, and

**bitCount(X)**is the number of ones in binary of

**X**. Using built-in function

`__builtin_parityll()`

of GNU C++ Compiler or doing some precalc we can find **det(D**in

_{a,b}) mod 2**O(1)**for each

**(a, b)**after precomputing

**det(Q**for all

_{a,c}) mod 2**a**and

**c**.

Applying Gauss-Jordan elimination to **Q _{a}** modulo 2 we can assume that it is represented in reduced row echelon form since elementary row operations do not change any of the determinants

**det(Q**. If rank of

_{a,c}) mod 2**Q**is less than

_{a}**N**then all determinants

**det(Q**are zero. Otherwise

_{a,c}) mod 2**Q**could be obtained from identity matrix by inserting some column

_{a}**G = {G[1], …, G[N]}**at some position (let it be

**k**-th column of

**Q**). Then

_{a}**det(Q**for

_{a,c}) mod 2 = G[c]**1 ≤ c < k**,

**det(Q**for

_{a,c}) mod 2 = 1**c = k**, and

**det(Q**for

_{a,c}) mod 2 = 0**k < c ≤ N+1**.

Since Gauss-Elimination could be performed in **O(N ^{2})** time using bitwise operations we get the solution with complexity

**O(B * N**.

^{2}+ B^{2})### EXPLANATION:

##The case N = 1

In this case the matrix **C _{a,b}** has only one element and it equals to

**Q**.

_{a}[1][1] * Q_{b}[1][1]We have only one permutation

**p = {1}**in this case.

Hence, the pair

**(a, b)**is good if and only if

**C**is odd, which is equivalent to the oddness of both numbers

_{a,b}[1][1]**Q**and

_{a}[1][1]**Q**.

_{b}[1][1]This observation allows to come up with

**O(B)**solution for this special case. Let

**M**be the number of odd values among

**{Q**. Since every good pair corresponds to some pair of odd numbers in this list, then the number of good pairs is

_{1}[1][1], Q_{2}[1][1], …, Q_{B}[1][1]}**M * (M − 1) / 2**and we are done.

From now on we assume that **N ≥ 2**.

##Reduction to the determinant

For the given pair **(a, b)** we construct another matrix such that its determinant is odd if and only if the pair **(a, b)** is good. Namely, let **D _{a,b}[i][j] = (C_{a,b}[i][j] + 1) mod 2**. Then for each permutation

**p = {p[1], p[2], …, p[N]}**the product

**Product[D**is zero if and only if we have at least one odd element among

_{a,b}[i][p[i]] : 1 ≤ i ≤ N]**C**.

_{a,b}[i][p[i]]Indeed, when all they are even then

**D**for all

_{a,b}[i][p[i]] = 1**i**and the product equals to

**1**.

On the other hand, when we have at least one odd element, say

**C**, then

_{a,b}[i][p[i]]**D**and the product is zero.

_{a,b}[i][p[i]] = 0Hence, the sum of these products over all permutations equals to the number of permutations **p**, for which the sequence **Tr(p)** has all even elements, which is equal to **N! − CNT(a, b)**.

Now the trick is that modulo 2 this sum coincide with the determinant of **D _{a,b}** which is denoted as

**det(D**. Indeed, determinant also equals to the sum of these products over all permutations but each product is taken with some sign. But

_{a,b})**-1**and

**1**has the same parity hence we can ignore signs when consider

**det(D**.

_{a,b}) mod 2Since **N!** is even when **N ≥ 2** (that is one of the reasons to handle the case **N = 1** separetely) then we get **det(D _{a,b}) mod 2 = CNT(a,b) mod 2**.

Therefore, the pair **(a, b)** is good if and only if **det(D _{a,b}) mod 2 = 1**.

This observation allows to get a solution with complexity **O(B ^{2} * N^{3})** but this of course is too slow. We can optimize it to

**O(B**using some bitwise operations but this still will be too slow.

^{2}* N^{2})##Representing Da,b as a product of matrices

Note that **D _{a,b}[i][j] = (C_{a,b}[i][j] + 1) mod 2**

= (Sum[Q_{a}[i][k] * Q_{b}[j][k] : 1 ≤ k ≤ N] + 1) mod 2

= Sum[Q_{a}[i][k] * Q_{b}[j][k] : 1 ≤ k ≤ N+1] mod 2

if we put

**Q**for all

_{c}[i][N+1] = 1**c**and

**i**.

In other words, we add column composed of ones to each matrix

**Q**.

_{c}###
So let’s assume that each **Q**_{c} is actually **N × (N+1)** matrix having last column composed of ones.

_{c}

This observation allows us to look at **D _{a,b}** from another point of view.

Namely,

**D**, where

_{a,b}= (Q_{a})^{T}* Q_{b}mod 2**A**denotes the matrix transpose to the matrix

^{T}**A**and star here is the standard matrix multiplication.

##Cauchy and Binet will save us

Now using Cauchy-Binet formula and the property **det(A) = det(A ^{T})** we get

**det(D**,

_{a,b}) mod 2 = Sum[det(Q_{a,c}) * det(Q_{b,c}) : 1 ≤ c ≤ N+1] mod 2where

**Q**is the matrix obtained from

_{a,c}**Q**by deleting its

_{a}**c**-th column.

This observation gives **O(B * N ^{3} + B^{2})** solution in the following way. We preprocess each matrix

**Q**by computing all the determinants

_{a}**det(Q**. Each determinant could be computed in

_{a,c}) mod 2**O(N**time using Gaussian elimination and bitwise operations (see below). Since we need

^{2})**N+1**determinants for each matrix this step takes

**O(B * N**operations in all.

^{3})Introducing numbers

**V _{a} = Sum[det(Q_{a,c}) mod 2 * 2^{c-1} : 1 ≤ c ≤ N+1]**

we can rewrite

**det(D**as

_{a,b}) mod 2**bitCount(V**, where

_{a}& V_{b}) mod 2**X & Y**is a bitwise “and” of the numbers

**X**and

**Y**, and

**bitCount(X)**is the number of ones in binary of

**X**. Since

**N ≤ 60**we can use 64-bit integer type to store

**V**. If you are using GNU C++ compiler then to calculate

_{a}**bitCount(X) mod 2**you can use built-in functions

`__builtin_parityll()`

that returns exactly this number or more well-known `__builtin_popcountll()`

that returns the number of ones in binary. They seem to be implemented very fast and are sufficient to keep the double loop over all pairs **(a, b)**fast enough. See author’s solution as a reference. Another way is to precompute bitCount values for numbers up to some small bound (

**2**or

^{16}**2**) and then divide number into several parts of almost equal length in binary and compute bitCount as a sum of bitCounts of these parts using precomputed tables.

^{21}But such solution also appears to be slow due to **O(B * N ^{3})** part (only mugurelionut was managed to optimize this enough to get AC).

##Gauss-Jordan elimination

The final step is to figure it out how to get the sequence **{det(Q _{a,c}) mod 2 : 1 ≤ c ≤ N+1}** in

**O(N**time.

^{2})For this we apply Gauss-Jordan elimination to the matrix

**Q**modulo 2.

_{a}That is, we reduce this matrix to reduced row echelon form using only elementary row operations performing all operations in the field

**Z**.

_{2}Note that each elementary row operation does not change any of the determinants

**det(Q**.

_{a,c}) mod 2Hence let’s assume that matrix

**Q**is already in its reduced row echelon form modulo 2.

_{a}At first we note that when rank of the matrix **Q _{a} mod 2** is less than

**N**than all these determinants are zero.

When rank is

**N**then its reduced row echelon form could be like this

100100 010000 001100 000010 000001

So it is obtained from identity matrix by inserting exactly one column. Moreover, if we insert the column **G = {G[1], …, G[N]}** to be the **k**-th column then we should have **G[i] = 0** for **i ≥ k** so that it will not ruin row echelon form, while values **G[1], …, G[k-1]** could be arbitrary. The inserted column is bold in the example above.

Now the funny thing is that

**det(Q _{a,c}) mod 2 = G[c]** for

**1 ≤ c < k**,

**det(Q**for

_{a,c}) mod 2 = 1**c = k**, and

**det(Q**for

_{a,c}) mod 2 = 0**k < c ≤ N+1**.

To see this we at first note that if **1 ≤ i _{1} < … < i_{L} < k** are positions of all ones in

**G**then

**G**is the sum of columns of the matrix

**Q**with indices

_{a}**i**. Hence if

_{1}, … i_{L}**c**is not equal to any of the

**i**and

_{1}, … i_{L}**k**then in the matrix

**Q**we have the column

_{a,c}**G**and it is the linear combination of other columns of

**Q**. Hence

_{a,c}**det(Q**in this case. When we delete

_{a,c}) mod 2 = 0**k**-th column from

**Q**we simply get the identity matrix; therefore

_{a}**det(Q**. Finally if

_{a,k}) mod 2 = 1**c**equals to one of the

**i**then all columns in

_{1}, … i_{L}**Q**are linearly independent since column

_{a,c}**G**can’t represented as sum of other columns; therefore

**det(Q**in this case. So we prove all formulas above.

_{a,c}) mod 2 = 1The Gauss-Jordan elimination modulo **2** could be performed in **O(N ^{2})** time using bitwise operation. For this we need represent each row of the matrix as 64-bit integer with binary form equal to this row. Then each pivoting could be made using “xor” operation in

**O(1)**time.

Thus we get the solution with complexity **O(B * N ^{2} + B^{2})** which is fast enough for this problem.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.