Gaussian Elimination

Gaussian elimination is a powerful technique for solving systems of linear equations and simplifying matrices through linear transformations. The Gauss-Jordan method specifically transforms a matrix into diagonal form, which serves as the foundation for computing determinants.

The algorithm proceeds as follows:

• For variables \(x_1, x_2, \ldots, x_n\), select \(x_i\) as the pivot element in row \(i\), aiming to eliminate all coefficients of \(x_i\) except in row \(i\).
• Find a row \(p\) where \(a_{p,i} \neq 0\) and swap rows \(p\) and \(i\).
• Use row \(i\) to eliminate the coefficient of \(x_i\) from all other rows.

This process has time complexity \(O(n^3)\). If an equation \(a_ix_i = q_i\) results in both \(a_i = 0\) and \(q_i = 0\), then \(x_i\) becomes a free variable. However, if \(q_i \neq 0\), the system has no solution.

Matrix Inversion

The inverse of a matrix \(\mathrm{G}\), denoted as \(\mathrm{P}\), is uniquely defined such that \(G \times P = \mathrm{I}\). Since matrices represent linear transformations, finding the inverse involves transforming \(G\) into the identity matrix \(\mathrm{I}\).

To achieve this transformation, first convert \(G\) into diagonal form using Gaussian elimination. Apply identical row operations to matrix \(P\). Finally, multiply each row \(i\) of \(P\) by the modular inverse of \(a_i\).

This approach also runs in \(O(n^3)\) time.

Determinant Calculation

The determinant of matrix \(A\) is defined as: \[ \det(A) = \sum_{p}(-1)^{\tau(p)}\prod_{i=1}^n A_{i,p_i} \] where \(\tau(p)\) represents the number of inversions in permutation \(p\). Computing this directly is computationally expensive, so we rely on key properties:

1. Swapping two rows changes the sign of \(\det(A)\).
2. If two rows are identical, \(\det(A) = 0\).
3. Multiplying a row by constant \(c\) multiplies the determinant by \(c\).
4. Adding one row to another does not change the determinant value.

Using these properties, we can compute the determinant via Gaussian elimination. During reduction to diagonal form, track row swaps (which affect signs) and multiply diagonal elements together.

In cases without guaranteed modular inverses (e.g., non-prime modulus), use Euclidean division instead. Each operation reduces a row element by at least half, leading to \(O(n^2 \log p)\) operations overall. Total complexity becomes \(O(n^3 + n^2 \log p)\).

for(int i = 1; i <= n; i++){
    for(int j = i + 1; j <= n; j++){
        while(a[i][i]){
            ll q = a[j][i] / a[i][i];
            for(int k = i; k <= n; k++) 
                ADD(a[j][k], mod - q * a[i][k] % mod);
            swap(a[i], a[j]); 
            fl ^= 1;
        } 
        swap(a[i], a[j]); 
        fl ^= 1;
    }
}
for(int i = 1; i <= n; i++) 
    MUL(ans, a[i][i]);
if(fl) 
    MUL(ans, mod - 1);

Additional determinant properties include:

5. \(|AB| = |A| \times |B|\)

Matrix-Tree Theorem

For directed graph \(G\), define its in-degree Laplacian matrix \(L_{in}\) as:

• If \(i = j\): \(L_{in_{i,i}} = \deg_{in_i}\)
• If \(i \neq j\): \(L_{in_{i,j}} = -G_{i,j}\)

(Where \(G_{i,j}\) is the adjacency matrix of \(G\))

Matrix-Tree Theorem: The cofactor of \(L_{in_{r,r}}\) equals the count of leaf-oriented spanning trees rooted at node \(r\) (denoted \(T^{leaf}(r)\)).

A cofactor of matrix \(A\) at position \(A_{i,j}\) refers to the determinant of submatrix obtained by removing row \(i\) and column \(j\), where indices range over \([n] = \{1, 2, \dots, n\}\).

Proof Sketch: Without loss of generality, assume root \(r = 1\). Every vertex except \(1\) requires exactly one incoming edge, initially giving \(\prod_{i=2}^n \deg_i\) configurations. Cycles must be excluded via inclusion-exclusion principles.

Define permutation \(p = \{p_1, p_2, \dots, p_n\}\) to describe fixed cycles:

• If \(p_i = i\), vertex \(i\) avoids cycles, contributing factor \(\deg_i\).
• If \(p_i \neq i\), it indicates a cycle transition from \(i\) to \(p_i\), contributing edge weight \(G_{i,j}\).

Let \(f(p)\) denote the number of cycles in \(p\), and \(g(p)\) the total vertices involved. Then the configuration count becomes: \[ \sum_p (-1)^{f(p)-g(p)} \prod_{i=2}^n L_{in_{i,j}} \] Each cyclic vertex contributes a negative sign to the Laplacian matrix.

Rearranging terms reveals equivalence to standard determinant computation: \[ \sum_p(-1)^{\tau(p)} \prod_{i=2}^n L_{in_{i,j}} = L_{in_{i,j}[n]\setminus\{i\}, [n]\setminus\{j\}} \] which confirms the theorem's validity.

Analogously, out-degree Laplacian \(L_{out}\) yields root-oriented spanning trees. For undirected graphs, this counts general spanning trees. Weighted edges modify adjacency entries accordingly, enabling calculation of \(\sum_T \prod_{e \in T} w_e\). Degree values adjust to reflect summed edge weights, with multiple edges combined additively per addition principle.

For tree-weight definitions based on product edge weights, update \(L_{i,j} = -w_{i,j}\) and \(L_{i,i} = \sum_{e=(i,v)} w_e\), followed by standard Matrix-Tree application.

When weights represent additive combinations, construct set power series like \((1 + x^w)\), yielding \(O(n^3V)\) performance. However, leveraging linearity allows fixing individual edges while assigning unit weights elsewhere, reducing effective dimensionality. Constructing generating functions like \((wx + 1)\) enables efficient multiplication truncation beyond degree one, restoring \(O(n^3)\) behavior.

Further extensions support convolution-based weight schemes using polynomial representations \((1 + x^w)\), achieving \(O(n^3 \times T(V))\) complexity, where \(T(V)\) denotes convolution cost for size-\(V\) inputs.

Certain specializations benefit significantly from optimization techniques. Bitwise convolutions typically require \(O(n^3 V \log V)\) time due to Fast Walsh-Hadamard Transform (FWHT). Precomputing FWHT-transformed edge weights and applying separate Matrix-Tree computations per bit dimension followed by inverse transformation yields improved \(O(n^3 V + n^2 V \log V)\) efficiency. Similar acceleration applies broadly across linear transformations.

ll det(){
    ll ans = 1;
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++) 
            if(a[j][i]){
                swap(a[j], a[i]); 
                ans = mod - ans; 
                break;
            }
        if(!a[i][i]) return 0;
        ll c = qpow(a[i][i], mod - 2);
        for(int j = i + 1; j <= n; j++){
            ll q = a[j][i] * c % mod;
            for(int k = i; k <= n; k++) 
                ADD(a[j][k], mod - q * a[i][k] % mod);
        }
    }
    for(int i = 1; i <= n; i++) 
        MUL(ans, a[i][i]);
    return ans;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> t;
    for(int i = 1; i <= m; i++){
        int x, y, w; 
        cin >> x >> y >> w;
        if(t == 0){
            ADD(L[x][y], mod - w); 
            ADD(L[y][x], mod - w);
            ADD(L[x][x], w); 
            ADD(L[y][y], w);
        } else{
            ADD(L[x][y], mod - w); 
            ADD(L[y][y], w);
        }
    }
    for(int i = 1; i < n; i++)
        for(int j = 1; j < n; j++)
            a[i][j] = L[i + 1][j + 1];
    n--;
    cout << det();
    return 0;
}

BEST Theorem

The BEST theorem connects Eulerian circuit enumeration with spanning tree counting in directed Eulerian graphs. Specifically, the number of distinct Eulerian circuits (considering rotational equivalence) is given by:

Proof Outline:

Assign combinatorial meaning: choose the starting point as the root. Observe that each vertex's final outgoing edge collectively forms a root-oriented spanning tree. Assigning tree edges as last-used ensures non-tree edges follow a fixed orrder, contributing \(\prod (\deg_i - 1)\) possibilities. Establishing bijective correspondence proves correctness.

Every Eulerian tour maps uniquely to such a configuration. Conversely, every valid spanning tree corresponds to an actual Eulerian traversal since unvisited edges would violate balance conditions inherent to Eulerian structures. Thus, the mapping constitutes a bijection.