Rezolvare PBinfo #2225

Se consideră o matrice binară cu n linii și m coloane. Spunem că două linii L1, L2 din matrice sunt complementare dacă a[L1][j] ≠ a[L2][j], pentru orice j=1..m (adică acolo unde pe linia L1 este 0, pe linia L2 este 1 și invers).

Cerința

Să se determine numărul de perechi de linii (L1, L2) cu L1 < L2 cu proprietatea că sunt complementare.

Date de intrare

Fișierul de intrare complementar.in conține pe prima linie numerele n și m. Pe următoarele n linii, fără spații între ele, sunt câte m de valori binare.

Date de ieșire

Fișierul de ieșire complementar.out va conține un singur număr natural reprezentând numărul perechi de linii complementare.

Restricții și precizări

• 1 ≤ n ≤ 200 000
• 4 ≤ m ≤ 30

Exemplu:

complementar.in

5 6
101001
010110
010110
111111
000000

complementar.out

3

Explicație

Cele trei perechi de linii complementare sunt (1,2), (1,3) și (4,5).