📊 Матрици: Разширени теореми и приложения

Матриците са фундаментални структури в състезателното програмиране, появяващи се в различни контексти - от оптимизация на динамично програмиране до теория на графите и теория на числата. Отвъд основните операции, няколко мощни теореми и техники използват свойствата на матриците за ефективно решаване на сложни задачи.

Това изчерпателно ръководство обхваща: - Теорема на Кирхоф (Matrix Tree Theorem) за броене на покриващи дървета - Теорема на Кейли-Хамилтън за оптимизация на матрични полиноми - Гаусова елиминация над различни полета (реални, модулни, двоични) - Матрично степенуване за рекурентни зависимости - Специални типове матрици и техните свойства - Практични имплементации и оптимизации

🧮 Основи на матриците

Основни матрични операции

struct Matrix {
    int n, m;
    vector<vector<long long>> a;

    Matrix(int _n, int _m) : n(_n), m(_m) {
        a.assign(n, vector<long long>(m, 0));
    }

    Matrix(vector<vector<long long>> _a) : a(_a) {
        n = a.size();
        m = a[0].size();
    }

    // Единична матрица
    static Matrix identity(int n) {
        Matrix I(n, n);
        for (int i = 0; i < n; i++) {
            I.a[i][i] = 1;
        }
        return I;
    }

    // Събиране на матрици
    Matrix operator+(const Matrix& other) const {
        Matrix result(n, m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                result.a[i][j] = a[i][j] + other.a[i][j];
            }
        }
        return result;
    }

    // Умножение на матрици
    Matrix operator*(const Matrix& other) const {
        Matrix result(n, other.m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < other.m; j++) {
                for (int k = 0; k < m; k++) {
                    result.a[i][j] += a[i][k] * other.a[k][j];
                }
            }
        }
        return result;
    }

    // Умножение със скалар
    Matrix operator*(long long scalar) const {
        Matrix result(n, m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                result.a[i][j] = a[i][j] * scalar;
            }
        }
        return result;
    }

    // Транспониране
    Matrix transpose() const {
        Matrix result(m, n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                result.a[j][i] = a[i][j];
            }
        }
        return result;
    }
};

Матрично степенуване

Една от най-мощните техники в състезателното програмиране е матричното степенуване за решаване на линейни рекурсии:

const long long MOD = 1e9 + 7;

struct MatrixMod {
    int n;
    vector<vector<long long>> a;

    MatrixMod(int _n) : n(_n) {
        a.assign(n, vector<long long>(n, 0));
    }

    static MatrixMod identity(int n) {
        MatrixMod I(n);
        for (int i = 0; i < n; i++) I.a[i][i] = 1;
        return I;
    }

    MatrixMod operator*(const MatrixMod& other) const {
        MatrixMod result(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    result.a[i][j] = (result.a[i][j] + 
                                     a[i][k] * other.a[k][j]) % MOD;
                }
            }
        }
        return result;
    }

    MatrixMod power(long long p) const {
        MatrixMod result = identity(n);
        MatrixMod base = *this;

        while (p > 0) {
            if (p & 1) result = result * base;
            base = base * base;
            p >>= 1;
        }

        return result;
    }
};

// Пример: Фибоначи чрез матрично степенуване
// F(n) = F(n-1) + F(n-2)
// [F(n+1)]   [1 1]^n   [F(1)]   [1 1]^n   [1]
// [F(n)  ] = [1 0]   * [F(0)] = [1 0]   * [0]

long long fibonacci(long long n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    MatrixMod M(2);
    M.a[0][0] = M.a[0][1] = M.a[1][0] = 1;
    M.a[1][1] = 0;

    M = M.power(n);
    return M.a[1][0];  // F(n)
}

int main() {
    cout << "F(10) = " << fibonacci(10) << "\n";      // 55
    cout << "F(100) = " << fibonacci(100) << "\n";    // Много голямо число
    return 0;
}

Времева сложност: $O(n^3 \log p)$ където $n$ е размерът на матрицата и $p$ е степента.

Приложения: - Линейни рекурсии: Фибоначи, трибоначи и др. - Броене на пътища в граф: Брой пътища с дължина $k$ - Оптимизация на динамично програмиране - Линейни трансформации

🌳 Теорема на Кирхоф (Matrix Tree Theorem)

Теоремата на Кирхоф е един от най-елегантните резултати в теорията на графите, предоставящ директен алгебричен метод за броене на покриващите дървета в граф.

Формулировка на теоремата

Броят на покриващите дървета в свързан граф $G = (V, E)$ е равен на произволен кофактор на неговата Лапласова матрица $L$.

Лапласова матрица

За граф с $n$ върха:

Матрица на степените $D$: Диагонална матрица където $D_{i,i} = \deg(v_i)$

Матрица на съседство $A$: $A_{i,j} = $ брой ребра между $v_i$ и $v_j$

Лапласова матрица: $L = D - A$

Експлицитно: $$L_{i,j} = \begin{cases} \deg(v_i) & \text{ако } i = j \\ -(\text{брой ребра между } i \text{ и } j) & \text{ако } i \neq j \end{cases}$$

Изчисляване на броя покриващи дървета

#include <bits/stdc++.h>
using namespace std;

const double EPS = 1e-9;

// Изчисли детерминанта чрез гаусова елиминация
double determinant(vector<vector<double>> A) {
    int n = A.size();
    double det = 1.0;

    for (int i = 0; i < n; i++) {
        // Намери пивот
        int pivot = i;
        for (int j = i + 1; j < n; j++) {
            if (abs(A[j][i]) > abs(A[pivot][i])) {
                pivot = j;
            }
        }

        if (abs(A[pivot][i]) < EPS) {
            return 0;  // Сингулярна матрица
        }

        if (pivot != i) {
            swap(A[i], A[pivot]);
            det *= -1;  // Промяна на знака при размяна на редове
        }

        det *= A[i][i];

        // Елиминирай колоната
        for (int j = i + 1; j < n; j++) {
            double factor = A[j][i] / A[i][i];
            for (int k = i; k < n; k++) {
                A[j][k] -= factor * A[i][k];
            }
        }
    }

    return det;
}

// Брой покриващи дървета използвайки теоремата на Кирхоф
long long countSpanningTrees(int n, vector<pair<int, int>>& edges) {
    // Построй Лапласова матрица
    vector<vector<double>> L(n, vector<double>(n, 0));

    for (auto [u, v] : edges) {
        L[u][u]++;
        L[v][v]++;
        L[u][v]--;
        L[v][u]--;
    }

    // Премахни първия ред и колона (изчисли кофактор)
    vector<vector<double>> cofactor(n - 1, vector<double>(n - 1));
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            cofactor[i - 1][j - 1] = L[i][j];
        }
    }

    // Детерминантата дава броя покриващи дървета
    double result = determinant(cofactor);
    return (long long)(result + 0.5);  // Закръгли до най-близкото цяло
}

int main() {
    // Пример: K4 (пълен граф с 4 върха)
    // Известен отговор: 16 покриващи дървета
    int n = 4;
    vector<pair<int, int>> edges = {
        {0, 1}, {0, 2}, {0, 3},
        {1, 2}, {1, 3}, {2, 3}
    };

    cout << "Покриващи дървета в K4: " << countSpanningTrees(n, edges) << "\n";
    // Изход: 16

    return 0;
}

Времева сложност: $O(n^3)$ за гаусовата елиминация

Модулна версия

За големи графи изчислете детерминантата по модул просто число:

const long long MOD = 1e9 + 7;

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

long long modInv(long long a, long long mod) {
    return modPow(a, mod - 2, mod);  // Малката теорема на Ферма
}

long long determinantMod(vector<vector<long long>> A, long long mod) {
    int n = A.size();
    long long det = 1;

    for (int i = 0; i < n; i++) {
        int pivot = -1;
        for (int j = i; j < n; j++) {
            if (A[j][i] % mod != 0) {
                pivot = j;
                break;
            }
        }

        if (pivot == -1) return 0;

        if (pivot != i) {
            swap(A[i], A[pivot]);
            det = (mod - det) % mod;
        }

        det = (det * A[i][i]) % mod;
        long long inv = modInv(A[i][i], mod);

        for (int j = i + 1; j < n; j++) {
            long long factor = (A[j][i] * inv) % mod;
            for (int k = i; k < n; k++) {
                A[j][k] = ((A[j][k] - factor * A[i][k]) % mod + mod) % mod;
            }
        }
    }

    return det;
}

long long countSpanningTreesMod(int n, vector<pair<int, int>>& edges) {
    vector<vector<long long>> L(n, vector<long long>(n, 0));

    for (auto [u, v] : edges) {
        L[u][u]++;
        L[v][v]++;
        L[u][v] = (L[u][v] - 1 + MOD) % MOD;
        L[v][u] = (L[v][u] - 1 + MOD) % MOD;
    }

    vector<vector<long long>> cofactor(n - 1, vector<long long>(n - 1));
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            cofactor[i - 1][j - 1] = L[i][j];
        }
    }

    return determinantMod(cofactor, MOD);
}

Приложения

Броене на етикетирани дървета: $n^{n-2}$ (формула на Кейли, доказуема чрез теоремата на Кирхоф)
Надеждност на мрежата: Брой начини за поддържане на свързаност
Електрически мрежи: Свързано с ефективното съпротивление
Случайни покриващи дървета: Алгоритми за равномерно вземане на проби

🏁 Гаусова елиминация по модул 2 (XOR системи)

Когато работим над $GF(2)$ (двоичното поле), събирането става XOR и можем да използваме побитови операции за масивни ускорения.

Двоична гаусова елиминация с bitset

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2000;
bitset<MAXN> matrix[MAXN];  // Всеки ред е bitset
bitset<MAXN> rhs;           // Дясна страна (за Ax = b)

int gaussianEliminationBinary(int n, int m) {
    // n = редове, m = колони
    int rank = 0;

    for (int col = 0; col < m && rank < n; col++) {
        // Намери пивот
        int pivot = -1;
        for (int row = rank; row < n; row++) {
            if (matrix[row][col]) {
                pivot = row;
                break;
            }
        }

        if (pivot == -1) continue;  // Колоната е цяла от нули

        // Размени редове
        swap(matrix[rank], matrix[pivot]);

        // Елиминирай всички други 1-ци в тази колона
        for (int row = 0; row < n; row++) {
            if (row != rank && matrix[row][col]) {
                matrix[row] ^= matrix[rank];  // XOR цели редове!
                rhs[row] = rhs[row] ^ rhs[rank];
            }
        }

        rank++;
    }

    return rank;
}

// Пример: Пъзел Lights Out
// n x n мрежа, кликването на светлина я превключва заедно със съседите
// Намерете дали конфигурацията е разрешима

bool lightsOut(int n, vector<vector<int>>& target) {
    int N = n * n;

    // Построй система от уравнения
    // Променлива x[i][j] = 1 ако кликнем на позиция (i,j)
    // Всяко уравнение: сума на кликванията, засягащи позицията = целево състояние

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int eq = i * n + j;  // Номер на уравнението
            rhs[eq] = target[i][j];

            // Кликването на (i,j) засяга себе си
            matrix[eq][i * n + j] = 1;

            // И съседите
            if (i > 0) matrix[eq][(i-1) * n + j] = 1;      // нагоре
            if (i < n-1) matrix[eq][(i+1) * n + j] = 1;    // надолу
            if (j > 0) matrix[eq][i * n + (j-1)] = 1;      // наляво
            if (j < n-1) matrix[eq][i * n + (j+1)] = 1;    // надясно
        }
    }

    int rank = gaussianEliminationBinary(N, N);

    // Провери консистентност: ако някое уравнение стана 0 = 1, няма решение
    for (int i = rank; i < N; i++) {
        if (rhs[i]) return false;
    }

    return true;
}

int main() {
    // Пример: 3x3 lights out
    vector<vector<int>> target = {
        {1, 0, 1},
        {0, 1, 0},
        {1, 0, 1}
    };

    if (lightsOut(3, target)) {
        cout << "Разрешимо!\n";
    } else {
        cout << "Няма решение\n";
    }

    return 0;
}

Ускорение: Операциите са $64 \times$ по-бързи поради оптимизациите на bitset! - Времева сложност: $O(n^3 / 64)$ вместо $O(n^3)$

Приложения на двоичната гаусова елиминация

Пъзел Lights Out: Класическо приложение
XOR подмножества: Намери подмножество с конкретен XOR
Линейни кодове: Кодове за коригиране на грешки
Криптоанализ: Разбиване на линейни шифри
Теория на игрите: Анализ на XOR игри (варианти на Nim)

Намиране на XOR подмножество

// Даден масив, намери дали съществува подмножество с XOR равен на цел
bool findXORSubset(vector<int>& arr, int target) {
    const int BITS = 30;  // Предполагаме 30-битови цели числа
    int n = arr.size();

    // Всяко число е ред в двоична матрица
    for (int i = 0; i < n; i++) {
        for (int bit = 0; bit < BITS; bit++) {
            matrix[i][bit] = (arr[i] >> bit) & 1;
        }
    }

    // Целта като дясна страна
    for (int bit = 0; bit < BITS; bit++) {
        rhs[bit] = (target >> bit) & 1;
    }

    int rank = gaussianEliminationBinary(n, BITS);

    // Провери дали системата е консистентна
    for (int i = rank; i < n; i++) {
        bool all_zero = true;
        for (int j = 0; j < BITS; j++) {
            if (matrix[i][j]) {
                all_zero = false;
                break;
            }
        }
        if (all_zero && rhs[i]) return false;
    }

    return true;
}

🎯 Теорема на Кейли-Хамилтън

Теоремата на Кейли-Хамилтън гласи, че всяка квадратна матрица удовлетворява собственото си характеристично уравнение.

Формулировка на теоремата

Ако $p(\lambda) = \det(A - \lambda I)$ е характеристичният полином на матрица $A$, тогава: $$p(A) = 0$$

Приложение: Бързо матрично степенуване

За $k \times k$ матрица, вместо да изчисляваме $A^n$ директно, можем да: 1. Намерим характеристичния полином $p(\lambda)$ 2. Редуцираме високите степени използвайки $p(A) = 0$ 3. Изразим $A^n$ като полином от степен $< k$

// За 2x2 матрица характеристичният полином е:
// p(λ) = λ² - tr(A)λ + det(A)
// Така A² = tr(A)·A - det(A)·I

MatrixMod fastPower2x2(MatrixMod A, long long n) {
    // За n > 2 използвай: A^n = c₁A + c₀I
    // Изчисли c₁, c₀ използвайки рекурентна зависимост

    long long trace = (A.a[0][0] + A.a[1][1]) % MOD;
    long long det = (A.a[0][0] * A.a[1][1] - A.a[0][1] * A.a[1][0]) % MOD;
    det = (det % MOD + MOD) % MOD;

    // Използвай матрично степенуване на рекурсията на коефициентите
    // Това е сложно, но спестява фактор на практика
    return A.power(n);  // Резервен вариант към стандартния метод
}

Забележка: На практика директното матрично степенуване често е по-просто, освен ако матрицата не е много голяма.

💡 Специални типове матрици

Симетрични матрици

$A = A^T$ (транспонираната е равна на себе си)

Свойства: - Винаги диагонализируеми - Собствените стойности са реални - Собствените вектори са ортогонални

Ортогонални матрици

$A^T A = I$ (транспонираната е обратна)

Свойства: - Запазват разстояния и ъгли - Детерминантата е $\pm 1$ - Ротации и отражения

Пермутационни матрици

Точно една 1 във всеки ред и колона, останалите 0.

Свойства: - Представят пермутации - $P^T = P^{-1}$ - Детерминантата е $\pm 1$

🚀 Разширени техники

Блоково умножение на матрици

За много големи матрици разделете на блокове:

// Алгоритъм на Щрасен: O(n^2.807) вместо O(n^3)
// Практичен за n > 64, но сложен за имплементация

Разредени матрици

За матрици с предимно нули:

struct SparseMatrix {
    map<pair<int,int>, long long> data;
    int n, m;

    long long get(int i, int j) {
        auto it = data.find({i, j});
        return (it == data.end()) ? 0 : it->second;
    }

    void set(int i, int j, long long val) {
        if (val != 0) {
            data[{i, j}] = val;
        } else {
            data.erase({i, j});
        }
    }
};

Верига от умножение на матрици

Намерете оптималния ред за умножение на матрици, за да минимизирате операциите:

// Класическа ДП задача
// dp[i][j] = минимална цена за умножение на матрици от i до j
int matrixChainOrder(vector<int>& dims) {
    int n = dims.size() - 1;
    vector<vector<int>> dp(n, vector<int>(n, 0));

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;

            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k+1][j] + 
                          dims[i] * dims[k+1] * dims[j+1];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }

    return dp[0][n-1];
}

📝 Практически задачи

Задача 1: Вариант на Фибоначи

Изчислете $F(n) = 2F(n-1) + 3F(n-2)$ с $F(0) = 1, F(1) = 1$.

long long fibVariant(long long n) {
    if (n == 0) return 1;
    if (n == 1) return 1;

    MatrixMod M(2);
    M.a[0][0] = 2; M.a[0][1] = 3;
    M.a[1][0] = 1; M.a[1][1] = 0;

    M = M.power(n);
    return M.a[1][0];
}

Задача 2: Броене на пътища

Броете пътища с точна дължина $k$ в граф.

long long countPaths(vector<vector<int>>& adj, int k, int start, int end) {
    int n = adj.size();
    MatrixMod A(n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            A.a[i][j] = adj[i][j];
        }
    }

    A = A.power(k);
    return A.a[start][end];
}

Задача 3: Покриващи дървета в мрежа

Броете покриващи дървета в $n \times m$ графова мрежа.

// Използвайте теоремата на Кирхоф върху Лапласовата матрица на графовата мрежа
// Отговорът има затворена форма за малки мрежи

🏁 Заключение

Теорията на матриците предоставя мощни инструменти за състезателно програмиране:

Ключови техники:

Матрично степенуване: $O(\log n)$ решение за линейни рекурсии
Фибоначи, ДП оптимизация, броене на пътища
Време: $O(k^3 \log n)$ за $k \times k$ матрица
Теорема на Кирхоф: Броене на покриващи дървета в $O(n^3)$
Превръщане на комбинаторика в линейна алгебра
Точни броения по модул просто число
Двоична гаусова елиминация: XOR системи в $O(n^3/64)$
Lights Out, XOR подмножество, теория на игрите
Bitset за 64× ускорение
Кейли-Хамилтън: Полиномно представяне на матрични степени
Редуцира изчисленията за специални матрици
По-скоро теоретичен инструмент от практически

Обобщение на сложността:

Операция	Времева сложност	Памет
Умножение на матрици	$O(n^3)$	$O(n^2)$
Матрично степенуване	$O(n^3 \log k)$	$O(n^2)$
Детерминанта	$O(n^3)$	$O(n^2)$
Гаусова елиминация	$O(n^3)$ или $O(n^3/64)$	$O(n^2)$
Брой покриващи дървета	$O(n^3)$	$O(n^2)$

Кога да използваме матрици:

Линейни рекурсии с голямо $n$: Използвайте матрично степенуване
Броене на пътища в графи: Степени на матрицата на съседство
Броене на покриващи дървета: Теорема на Кирхоф
XOR задачи: Двоична гаусова елиминация
ДП оптимизация: Матрично представяне на преходите

Матричните техники трансформират привидно сложни задачи в стандартни операции по линейна алгебра, предоставяйки елегантни и ефективни решения. Овладейте тези инструменти и ще имате значително предимство в напредналото състезателно програмиране!

Операция	Времева сложност	Памет
Умножение на матрици	\(O(n^3)\)	\(O(n^2)\)
Матрично степенуване	\(O(n^3 \log k)\)	\(O(n^2)\)
Детерминанта	\(O(n^3)\)	\(O(n^2)\)
Гаусова елиминация	\(O(n^3)\) или \(O(n^3/64)\)	\(O(n^2)\)
Брой покриващи дървета	\(O(n^3)\)	\(O(n^2)\)