линейные вычисления на очень большой матрице

Question

Нам нужно вычислить все линейные комбинации (двоичные числа по модулю 2) в строке матрицы

    [C1|C2|C3|C4|C5|C6|C7]
R1: [1 |0 | 0| 0| 0| 0|1 ]
R2: [1 |0 | 0| 0| 0| 0|1 ]
R3: [1 |0 | 0| 0| 0| 0|1 ]
R4: [1 |0 | 0| 0| 0| 0|1 ]

1) R1, R2, R3, R4

2) R1 + R2, R1 + R3, R1 + R4, R2 + R3, R2 + R4, R3, R4 +

3) R1 + R2 + R3, R1 + R2 + R4, R1 + R3 + R4

4) R1 + R2 + R3 + R4

i) ...

Я использовал биномиальное дерево, но оно действительно медленное, потому что матрица огромна (приблизительно ~ 50000 * 50000)

bool Util::binomialTree(int start, int end, int depth, 
        int *tab_index, vector<YNumber*> resultatY,  int size_factor, mpz_t n){
    int i;
    // tab_index contains all the index of the 
    // matrix and depth contains the index numbers in tab_index
    // computation here
    for (i = start + 1; i < end; i++){
            if (binomialTree (i, end, depth + 1,tab_index,
                        resultatY, size_factor, n)){
                return true;
            }
     }
    return false;
}

Можете ли вы предложить эффективный алгоритм?

Answer 1

Я имею в виду дерево префиксов, в котором символы являются координатами в матрице.при добавлении в дерево добавьте значение следующей координаты к значению родительского узла.таким образом, вам нужно будет только посчитать (R1 + R2 + R3) один раз для (R1 + R2 + R3 + R4) и (R1 + R2 + R3 + R4 + R5).

Надеюсь, это понятно...

Не могли бы вы объяснить, почему вы выбрали биномиальное дерево?