Interval/Timestamp Linear Basis: Elements are incorporated whenever feasible, only omitted when absolutely necessary.

Lindström–Gessel–Viennot Lemma Applications

This lemma serves as a powerful tool for calculating signed sums of non-intersecting paths. Its practical implementations include problems such as P7736 [NOI2021] Path Intersections and CF348D Turtles. The algorithm verifies the existence of non-intersecting paths through random weight assignments, with computational complexity equivalent to determinant calculation.

Matrix-Tree Theorem

The Matrix-Tree Theorem enables the determination of spanning tree counts within a graph, sharing computational complexity with determinant calculation methods.

Gauss-Jordan Elimination Method

A linear equation can be represented as [a₁, a₂, ..., aₙ, b]. The coefficeint matrix of a linear system is denoted as:

$$ \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \ a_{21} & a_{22} & \cdots & a_{2n} \ \vdots & \vdots & \ddots & \vdots \ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix} $$ The augmented matrix of the linear system is:

$$ \left[ \begin{array}{c|c} \begin{matrix} a_{11} & a_{12} & \cdots & a_{1n} \ a_{21} & a_{22} & \cdots & a_{2n} \ \vdots & \vdots & \ddots & \vdots \ a_{n1} & a_{n2} & \cdots & a_{nn} \end{matrix} & \begin{matrix} b_1 \ b_2 \ \vdots \ b_n \end{matrix} \end{array} \right] $$ The objective is to transform the coefficient matrix into diagonal form through these steps:

1. For each column i (in ascending order), locate a row x (not previously used, tracked via a selection array) with a non-zero value in column i. Swap this row with row i.
2. Use this row to zero out the i-th element in all other rows x ≠ i. This is achieved by subtracting (aₓᵢ/aᵢᵢ) × aₓₖ from each element aₓₖ.
3. After elimination, xᵢ = aᵢᵢ/bᵢ. If any row results in 0=0, there are infinitely many solutions. If any row results in 0≠0, there is no solution.

Implementation Code

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>

using namespace std;

const int MAX_SIZE = 55;
const double EPSILON = 1e-6;

vector<vector<double>> matrix(MAX_SIZE, vector<double>(MAX_SIZE + 1));
bitset<MAX_SIZE> used_rows;
int dimension;

int main() {
    cin >> dimension;
    
    for (int i = 0; i < dimension; i++) {
        for (int j = 0; j <= dimension; j++) {
            cin >> matrix[i][j];
        }
    }
    
    for (int col = 0; col < dimension; col++) {
        int pivot_row = -1;
        for (int row = 0; row < dimension; row++) {
            if (!used_rows[row] && abs(matrix[row][col]) > EPSILON) {
                pivot_row = row;
                break;
            }
        }
        
        if (pivot_row == -1) {
            continue;
        }
        
        swap(matrix[col], matrix[pivot_row]);
        used_rows[col] = true;
        
        double pivot_value = matrix[col][col];
        for (int row = 0; row < dimension; row++) {
            if (row == col || abs(matrix[row][col]) < EPSILON) continue;
            
            double factor = matrix[row][col] / pivot_value;
            for (int current_col = col; current_col <= dimension; current_col++) {
                matrix[row][current_col] -= factor * matrix[col][current_col];
            }
        }
    }
    
    for (int i = 0; i < dimension; i++) {
        if (abs(matrix[i][i]) < EPSILON && abs(matrix[i][dimension]) > EPSILON) {
            cout << "-1" << endl;
            return 0;
        }
    }
    
    for (int i = 0; i < dimension; i++) {
        if (abs(matrix[i][i]) < EPSILON && abs(matrix[i][dimension]) < EPSILON) {
            cout << "0" << endl;
            return 0;
        }
    }
    
    for (int i = 0; i < dimension; i++) {
        cout << "x" << (i + 1) << "=" << fixed << matrix[i][dimension] / matrix[i][i] << endl;
    }
    
    return 0;
}

Matrix Inversion

To find the inverse of matrix A, perform Gaussian elimination or Gauss-Jordan elimination on A while simultaneously applying identical operations to an identity matrix E. This works because the elimination process effectively multiplies A by A⁻¹, transforming E into A⁻¹.

Determinant Calculation via Gaussian Elimination

Using these determinant properties:

1. Swapping two rows (or columns) changes the sign of the determinant.
2. Adding k times a row (or column) to another row (or column) preserves the determinant value.

Apply Gaussian elimination to transform the determinant into a diagonal matrix. The determinant value is then the product of diagonal elements: ∏ᵢ₌₁ⁿ aᵢᵢ. If any column cannot be eliminated, the determinant is zero.

For modular arithmetic with non-prime moduli, direct inversion isnt possible. Instead, use the Euclidean algorithm approach on elements a[j][i] and a[i][i]:

1. Set a[j][i] as b and a[i][i] as a
2. Replace a with a mod b
3. Swap a and b
4. Update other columns k by subtracting floor(a[i][i]/a[j][i]) × a[j][k]

This ensures one element becomes zero. Note: Using Gauss-Jordan elimination may incorrectly yield zero determinants.

Complexity analysis:

• For row i elimination with row j, let x = aᵢᵢ, y = aⱼᵢ
• If x and y are multiples, elimination completes in two steps
• If y ≥ x, values swap in next iteration
• In both cases, x reduces by at least half each iteration
• Total complexity per row is O(n + log₂aᵢᵢ)
• Overall complexity is O(n²(n + log₂aᵢᵢ))

Implementation Code

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 605;
long long modulus;
vector<vector<long long>> matrix(MAX_SIZE, vector<long long>(MAX_SIZE));
bitset<MAX_SIZE> used_rows;
int dimension;
bool sign_changed = false;

int main() {
    cin >> dimension >> modulus;
    
    for (int i = 0; i < dimension; i++) {
        for (int j = 0; j < dimension; j++) {
            cin >> matrix[i][j];
            matrix[i][j] %= modulus;
        }
    }
    
    for (int col = 0; col < dimension; col++) {
        int pivot_row = -1;
        for (int row = 0; row < dimension; row++) {
            if (!used_rows[row] && matrix[row][col] != 0) {
                pivot_row = row;
                break;
            }
        }
        
        if (pivot_row == -1) {
            cout << "0" << endl;
            return 0;
        }
        
        swap(matrix[col], matrix[pivot_row]);
        if (col != pivot_row) sign_changed ^= 1;
        used_rows[col] = true;
        
        for (int row = col + 1; row < dimension; row++) {
            if (row == col) continue;
            
            while (matrix[row][col] != 0) {
                long long quotient = matrix[col][col] / matrix[row][col];
                for (int current_col = col; current_col < dimension; current_col++) {
                    matrix[col][current_col] = (matrix[col][current_col] - quotient * matrix[row][current_col] % modulus + modulus) % modulus;
                }
                swap(matrix[col], matrix[row]);
                sign_changed ^= 1;
            }
        }
    }
    
    long long result = 1;
    for (int i = 0; i < dimension; i++) {
        result = (result * matrix[i][i]) % modulus;
    }
    
    cout << (sign_changed ? ((modulus - 1) * result % modulus) : result) << endl;
    
    return 0;
}