Skip to content

Matrices

This article introduces a very important concept in linear algebra—Matrix—focusing on the properties of matrices, operations, and some applications of matrix multiplication.

Vectors and Matrices

In linear algebra, vectors are divided into column vectors and row vectors.

Warning

In the Chinese Taiwan region, the translation of "column" and "row" is exactly opposite to that in Mainland China. In OI Wiki, following the convention of Mainland China, we adopt the translation of column (column) and row (row).

The main objects of study in linear algebra are column vectors, conventionally denoted by bold lowercase letters. In contexts involving a large number of vectors and matrices in linear algebra, when no confusion arises, the vector notation above the letters can be omitted in handwriting.

Vectors are also special matrices. To represent a row vector, a transpose notation is written in the upper right corner of the bold lowercase letter. Row vectors in linear algebra generally represent equations.

Introduction

The introduction of matrices stems from systems of linear equations. Similar to vectors, matrices embody the idea of "packaging and processing" data.

For example, consider the system of linear equations:

\[ \begin{equation} \begin{cases} 7x_1+8x_2+9x_3=13 \\ 4x_1+5x_2+6x_3=12 \\ x_1+2x_2+3x_3=11 \end{cases} \end{equation} \]

Matrices are generally represented using parentheses or square brackets. Extracting the coefficients and writing them in matrix multiplication form:

\[ \begin{equation} \begin{pmatrix} 7 & 8 & 9 \\ 4 & 5 & 6 \\ 1 & 2 & 3 \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}=\begin{pmatrix} 13 \\ 12 \\ 11 \end{pmatrix} \end{equation} \]

Abbreviated as:

\[ Ax=b \]

That is, the unknown column vector x is left-multiplied by a matrix A to obtain the column vector b. This expression can be considered the fundamental form of linear algebra.

The primary computational model studied in linear algebra is the inner product. The inner product involves multiplication followed by summation, which is the process of a row vector left-multiplying a column vector to yield a scalar.

Matrix multiplication is an extension of the inner product. Matrix multiplication is equivalent to extracting a row from the left matrix and performing an inner product with a column extracted from the right matrix, resulting in the corresponding element of the product matrix. The mnemonic is "left row, right column."

When the object of study is the column vector on the right, matrix multiplication is equivalent to left-multiplying the column vector. From the perspective of left multiplication, a matrix transforms column vectors. In matrix multiplication, each column vector of the right matrix is transformed, correspondingly yielding each column vector of the result matrix.

A matrix can transform a single column vector, "package" transform a set of column vectors, or even transform the entire space—i.e., all column vectors. When a matrix is viewed as transforming the entire space, it transcends the space and becomes a pure transformation.

Definition

For a matrix \(A\), the main diagonal refers to the elements \(A_{i,i}\).

The identity matrix is generally denoted by \(I\), which has 1s on the main diagonal and 0s elsewhere.

Matrices of the Same Type

Two matrices with correspondingly equal numbers of rows and columns are called matrices of the same type.

Square Matrix

A matrix with an equal number of rows and columns is called a square matrix. A square matrix is a special type of matrix. The customary expression "matrix of order \(n\)" actually refers to an \(n \times n\) square matrix. Square matrices of the same order are matrices of the same type.

When studying systems of equations, vector groups, and the rank of matrices, general matrices are used. When studying eigenvalues and eigenvectors, as well as quadratic forms, square matrices are used.

Main Diagonal

The elements of a square matrix where the row index equals the column index constitute the main diagonal.

Symmetric Matrix

If the elements of a square matrix are symmetric about the main diagonal, i.e., for any \(i\) and \(j\), the element in row \(i\), column \(j\) equals the element in row \(j\), column \(i\), then the square matrix is called a symmetric matrix.

Diagonal Matrix

A square matrix where all elements off the main diagonal are \(0\) is called a diagonal matrix, generally denoted as:

\[ \operatorname{diag}\{\lambda_1,\cdots,\lambda_n\} \]

Here, \(\lambda_1,\cdots,\lambda_n\) are the elements on the main diagonal.

A diagonal matrix is a symmetric matrix.

If all elements of a diagonal matrix are \(1\), it is called the identity matrix, denoted by \(I\). As long as multiplication is defined, any matrix multiplied by the identity matrix remains unchanged, regardless of shape.

Triangular Matrix

If all elements below the main diagonal of a square matrix are \(0\), it is called an upper triangular matrix. If all elements above the main diagonal of a square matrix are \(0\), it is called a lower triangular matrix.

The product of two upper (lower) triangular matrices is still an upper (lower) triangular matrix. If the diagonal elements are all non-zero, then an upper (lower) triangular matrix is invertible, and its inverse is also an upper (lower) triangular matrix.

Unit Triangular Matrix

If an upper triangular matrix \(A\) has all diagonal elements equal to \(1\), it is called a unit upper triangular matrix. If a lower triangular matrix \(A\) has all diagonal elements equal to \(1\), it is called a unit lower triangular matrix.

The product of two unit upper (lower) triangular matrices is still a unit upper (lower) triangular matrix. The inverse of a unit upper (lower) triangular matrix is also a unit upper (lower) triangular matrix.

Operations

Linear Operations on Matrices

Linear operations on matrices include addition, subtraction, and scalar multiplication, all performed element-wise. Only matrices of the same type can be added or subtracted.

Transpose of a Matrix

The transpose of a matrix is denoted by a superscript "T" in the upper right corner, indicating that the rows and columns of the matrix are swapped.

A symmetric matrix remains unchanged after transposition.

Matrix Multiplication

Matrix multiplication is a generalization of the vector inner product.

Matrix multiplication is only defined when the number of columns of the first matrix equals the number of rows of the second matrix.

Let \(A\) be a \(P \times M\) matrix, \(B\) be an \(M \times Q\) matrix, and let matrix \(C\) be the product of matrices \(A\) and \(B\).

The element in the \(i\)-th row and \(j\)-th column of matrix \(C\) can be expressed as:

\[ C_{i,j} = \sum_{k=1}^MA_{i,k}B_{k,j} \]

In matrix multiplication, the number in the \(i\)-th row and \(j\)-th column of the result matrix \(C\) is obtained by multiplying and then summing the \(M\) numbers in the \(i\)-th row of matrix \(A\) with the \(M\) numbers in the \(j\)-th column of matrix \(B\). This multiply and sum process is the inner product of vectors. The number in the \(i\)-th row and \(j\)-th column of the product matrix is precisely the inner product of the \(i\)-th row vector of the multiplier matrix \(A\) and the \(j\)-th column vector of the multiplier matrix \(B\), summarized by the mnemonic left row, right column.

In linear algebra, vectors studied are mostly column vectors. According to this definition of matrix multiplication, left multiplication of a column vector by a matrix is frequently studied. This also reflects the idea of "packaging and processing," handling many vector inner products simultaneously.

Matrix multiplication satisfies the associative property but does not generally satisfy the commutative property.

Using the associative property, matrix multiplication can be optimized with the idea of fast exponentiation.

In competitions, since linear recurrence relations can be expressed in the form of matrix multiplication, matrix fast exponentiation is often used to find a specific term of a linear recurrence sequence.

Optimization

For relatively small matrices, consider manually unrolling loops to reduce constant factors.

Reordering loops can improve spatial locality. Such optimization does not change the time complexity of matrix multiplication but yields constant-level improvements.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Taking the reference code below as an example
mat operator*(const mat& T) const {
  mat res;
  for (int i = 0; i < sz; ++i)
    for (int j = 0; j < sz; ++j)
      for (int k = 0; k < sz; ++k) {
        res.a[i][j] += mul(a[i][k], T.a[k][j]);
        res.a[i][j] %= MOD;
      }
  return res;
}

// Better:
mat operator*(const mat& T) const {
  mat res;
  int r;
  for (int i = 0; i < sz; ++i)
    for (int k = 0; k < sz; ++k) {
      r = a[i][k];
      for (int j = 0; j < sz; ++j)
        res.a[i][j] += T.a[k][j] * r, res.a[i][j] %= MOD;
    }
  return res;
}

Inverse of a Square Matrix

The inverse matrix \(P\) of a square matrix \(A\) is the matrix such that \(A \times P = I\).

The inverse matrix may not exist. If it exists, it can be solved using Gaussian elimination.

Determinant of a Square Matrix

The determinant is an operation specific to square matrices.

Reference Code

Generally, a two-dimensional array can be used to simulate a matrix.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
struct mat {
  LL a[sz][sz];

  mat() { memset(a, 0, sizeof a); }

  mat operator-(const mat& T) const {
    mat res;
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j) {
        res.a[i][j] = (a[i][j] - T.a[i][j]) % MOD;
      }
    return res;
  }

  mat operator+(const mat& T) const {
    mat res;
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j) {
        res.a[i][j] = (a[i][j] + T.a[i][j]) % MOD;
      }
    return res;
  }

  mat operator*(const mat& T) const {
    mat res;
    int r;
    for (int i = 0; i < sz; ++i)
      for (int k = 0; k < sz; ++k) {
        r = a[i][k];
        for (int j = 0; j < sz; ++j)
          res.a[i][j] += T.a[k][j] * r, res.a[i][j] %= MOD;
      }
    return res;
  }

  mat operator^(LL x) const {
    mat res, bas;
    for (int i = 0; i < sz; ++i) res.a[i][i] = 1;
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j) bas.a[i][j] = a[i][j] % MOD;
    while (x) {
      if (x & 1) res = res * bas;
      bas = bas * bas;
      x >>= 1;
    }
    return res;
  }
};

Two Perspectives on Systems of Linear Equations

There are two perspectives for viewing matrix A, or transformation A.

The first perspective: Look at A row by row, observing each row of A. In this view, A is seen as a system of equations. This leads to the process of solving equations by elimination.

The second perspective: Look at A column by column, observing each column of A. A itself is composed of column vectors. In this view, transformation A is considered as a set of column vectors, and x is the unknown coefficients. The question becomes whether the set of column vectors in A, combined with the unknowns, can form the column vector b.

For example, the example at the beginning of the article becomes:

\[ \begin{equation} \begin{pmatrix} 7 \\ 4 \\ 1 \end{pmatrix}x_1+\begin{pmatrix} 8 \\ 5 \\ 2 \end{pmatrix}x_2+\begin{pmatrix} 9 \\ 6 \\ 3 \end{pmatrix}x_3=\begin{pmatrix} 13 \\ 12 \\ 11 \end{pmatrix} \end{equation} \]

Solving the equation becomes studying whether, by adjusting the three coefficients x, the given three basis vectors can combine to form the resulting vector.

The column-wise perspective is more novel than the row-wise perspective. From the column-wise perspective, linear independence and linear dependence can be studied.

Applications of Matrix Multiplication

Matrix Acceleration for Recurrences

Take the Fibonacci Sequence as an example. In the Fibonacci sequence, \(F_1 = F_2 = 1\), \(F_i = F_{i - 1} + F_{i - 2}(i \geq 3)\).

If a problem asks for the value of the \(n\)-th term of the Fibonacci sequence, the simplest method is direct recurrence. However, if \(n\) reaches the order of \(10^{18}\), recurrence is no longer feasible. In such cases, matrix acceleration can be considered.

According to the matrix form of the Fibonacci recurrence formula:

\[ \begin{bmatrix} F_{n-1} & F_{n-2} \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} F_n & F_{n-1} \end{bmatrix} \]

Define the initial matrix \(\text{ans} = \begin{bmatrix}F_2 & F_1\end{bmatrix} = \begin{bmatrix}1 & 1\end{bmatrix}, \text{base} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\). Then, \(F_n\) equals the element in the first row and first column of the matrix \(\text{ans} \text{base}^{n-2}\), i.e., the first row, first column element of \(\begin{bmatrix}1 & 1\end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-2}\).

Note

Matrix multiplication does not satisfy the commutative property, so it must not be written as the first row, first column element of \(\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-2} \begin{bmatrix}1 & 1\end{bmatrix}\). Additionally, for cases where \(n \leq 2\), simply output \(1\); matrix fast exponentiation is not needed.

Why multiply by the \(\text{base}\) matrix raised to the power of \(n-2\) instead of \(n\)? Because \(F_1\) and \(F_2\) can be obtained without matrix multiplication. That is, if only one multiplication is performed, \(F_3\) is already obtained. If it's still unclear why the exponent is \(n-2\), it is recommended to compute it manually.

Below is example code (core part) for finding the \(n\)-th term of the Fibonacci sequence modulo \(10^9+7\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
constexpr int mod = 1000000007;

struct Matrix {
  int a[3][3];

  Matrix() { memset(a, 0, sizeof a); }

  Matrix operator*(const Matrix &b) const {
    Matrix res;
    for (int i = 1; i <= 2; ++i)
      for (int j = 1; j <= 2; ++j)
        for (int k = 1; k <= 2; ++k)
          res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
    return res;
  }
} ans, base;

void init() {
  base.a[1][1] = base.a[1][2] = base.a[2][1] = 1;
  ans.a[1][1] = ans.a[1][2] = 1;
}

void qpow(int b) {
  while (b) {
    if (b & 1) ans = ans * base;
    base = base * base;
    b >>= 1;
  }
}

int main() {
  int n = read();
  if (n <= 2) return puts("1"), 0;
  init();
  qpow(n - 2);
  println(ans.a[1][1] % mod);
}

Here is a slightly more complex example.

\[ \begin{gathered} f_{1} = f_{2} = 0\\ f_{n} = 7f_{n-1}+6f_{n-2}+5n+4\times 3^n \end{gathered} \]

We observe that \(f_n\) is related to \(f_{n-1}, f_{n-2}, n\), so consider constructing a matrix to describe the state.

However, if the matrix only contains these three elements \(\begin{bmatrix}f_n& f_{n-1}& n\end{bmatrix}\), it is difficult to construct the transition equation because exponentiation and \(+1\) cannot be described by matrices.

Thus, consider constructing a larger matrix.

\[ \begin{bmatrix}f_n& f_{n-1}& n& 3^n & 1\end{bmatrix} \]

We want to construct a transition matrix that transforms to

\[ \begin{bmatrix} f_{n+1}& f_{n}& n+1& 3^{n+1} & 1 \end{bmatrix} \]

The transition matrix is

\[ \begin{bmatrix} 7 & 1 & 0 & 0 & 0\\ 6 & 0 & 0 & 0 & 0\\ 5 & 0 & 1 & 0 & 0\\ 12 & 0 & 0 & 3 & 0\\ 5 & 0 & 1 & 0 & 1 \end{bmatrix} \]

Matrix Representation of Modifications

「THUSCH 2017」The Great Magician

The great magician Little L created \(n\) magic crystal balls, each with energy values in three attributes: water, fire, and earth. Little L arranged these \(n\) crystal balls in a row from front to back on the ground and began today's magic performance.

Let \(A_i,\ B_i,\ C_i\) represent the water, fire, and earth energy values, respectively, of the \(i\)-th crystal ball from the front (index starting from 1).

Little L plans to perform \(m\) spells. Each time, he selects an interval \([l, r]\) and casts one of the following 3 major categories, 7 types of spells:

  1. Magic Excitation: Causes the energy of a specific attribute in each crystal ball in the interval to erupt, thereby enhancing another specific attribute. Specifically, there are three possible forms:

    • Fire element excites water element energy: Set \(A_i = A_i + B_i\).
    • Earth element excites fire element energy: Set \(B_i = B_i + C_i\).

    • Water element excites earth element energy: Set \(C_i = C_i + A_i\).

      Note that enhancing one attribute's energy does not change another attribute's energy. For example, \(A_i = A_i + B_i\) does not increase or decrease \(B_i\).

  2. Magic Enhancement: Little L waves his wand, consuming \(v\) points of his own mana to change the specific attribute energy of each crystal ball in the interval. Specifically, there are three possible forms:

    • Fire element energy fixed enhancement: Set \(A_i = A_i + v\).
    • Water element energy doubling enhancement: Set \(B_i=B_i \cdot v\).
    • Earth element energy absorption fusion: Set \(C_i = v\).

  3. Magic Release: Little L gathers the energy of all crystal balls in the interval, fusing them into a new crystal ball, which is then given to the audience. The energy value of each attribute of the generated crystal ball equals the algebraic sum of the corresponding energy values of all crystal balls in the interval. Note that the magic release process does not actually change the energy of the crystal balls in the interval.

It is worth mentioning that the raw materials for the crystal balls made and fused by Little L are custom-made OI factory crystals, so these crystal balls have an energy threshold of \(998244353\). When the energy value of an attribute in a crystal ball is greater than or equal to this threshold, the energy value automatically modulo the threshold to avoid explosion.

Little W, the (only) audience member, watched the entire performance and received each crystal ball fused by Little L during the performance. Little W wants to know the energy values of the three attributes contained in these crystal balls.

Due to the associative and distributive properties of matrices, single-point modifications naturally extend to intervals. That is, after deriving the matrix, a segment tree can be used directly to maintain the product of matrices over intervals.

Here are a few examples.

Transition for \(A_i = A_i + v\)

\[ \begin{bmatrix} A & B & C & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ v & 0 & 0 & 1\\ \end{bmatrix}= \begin{bmatrix} A+v & B & C & 1\\ \end{bmatrix} \]

Transition for \(B_i=B_i \cdot v\)

\[ \begin{bmatrix} A & B & C & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & v & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ \end{bmatrix}= \begin{bmatrix} A & B \cdot v & C & 1\\ \end{bmatrix} \]
「LibreOJ 6208」Tree Queries

There is a tree with \(n\) nodes, rooted at node \(1\). Each node has two weights \(k_i, t_i\), both initially \(0\).

Three operations are given:

  1. \(\operatorname{Add}( x , d )\) operation: For all nodes on the path from \(x\) to the root, set \(k_i\leftarrow k_i + d\)
  2. \(\operatorname{Mul}( x , d )\) operation: For all nodes on the path from \(x\) to the root, set \(t_i\leftarrow t_i + d \times k_i\)

  3. \(\operatorname{Query}( x )\) operation: Query the weight \(t_x\) of node \(x\)

    \(n,~m \leq 100000, ~-10 \leq d \leq 10\)

If thought directly, propagating operations and maintaining information is not straightforward. However, matrices can easily express this.

\[ \begin{aligned} \begin{bmatrix}k & t & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ d & 0 & 1 \end{bmatrix} &= \begin{bmatrix}k+d & t & 1 \end{bmatrix}\\ \begin{bmatrix}k & t & 1 \end{bmatrix} \begin{bmatrix} 1 & d & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} &= \begin{bmatrix}k & t+d \times k & 1 \end{bmatrix} \end{aligned} \]

Fixed-Length Path Counting

Problem Description

Given an \(n\)-vertex directed graph with all edge weights equal to \(1\), and an integer \(k\), your task is to find, for all pairs \((u,v)\), the number of paths from \(u\) to \(v\) of length exactly \(k\) (not necessarily simple paths, i.e., vertices or edges may be traversed multiple times).

We represent this graph with an adjacency matrix \(G\) (for an edge \((u\to v)\), set \(G[u,v]=1\), and \(0\) elsewhere; if there are multiple edges, set \(G[u,v]\) to the number of multiple edges). This matrix represents the directed graph. The following algorithm also applies to graphs with self-loops.

Clearly, this adjacency matrix corresponds to the answer for \(k=1\).

Suppose we know the matrix representing the number of paths of length \(k\), denoted as \(C_k\), and we want to find \(C_{k+1}\). Clearly, the DP transition equation is

\[ C_{k+1}[i,j] = \sum_{p = 1}^{n} C_k[i,p] \cdot G[p,j] \]

We can view this as matrix multiplication, so the above transition can be described as

\[ C_{k+1} = C_k \cdot G \]

Expanding this recurrence yields

\[ C_k = \underbrace{G \cdot G \cdots G}_{k \text{ times}} = G^k \]

To compute this matrix power, we can use the idea of fast exponentiation (binary exponentiation), achieving a time complexity of \(O(n^3 \log k)\).

Fixed-Length Shortest Path

Problem Description

Given an \(n\)-vertex weighted directed graph and an integer \(k\). For each pair \((u,v)\), find the length of the shortest path from \(u\) to \(v\) containing exactly \(k\) edges (not necessarily simple paths, i.e., vertices or edges may be traversed multiple times).

We still construct the adjacency matrix \(G\) of the graph, where \(G[i,j]\) represents the edge weight from \(i\) to \(j\). If there is no edge between \(i\) and \(j\), then \(G[i,j]=\infty\). (In case of multiple edges, take the minimum edge weight.)

Clearly, the above matrix corresponds to the answer for \(k=1\). Assume we know the answer for \(k\), denoted as matrix \(L_k\). Now we want the answer for \(k+1\). Clearly, the transition equation is

\[ L_{k+1}[i,j] = \min_{1\le p \le n} \left\{L_k[i,p] + G[p,j]\right\} \]

In fact, we can analogize this to matrix multiplication, noting that the above transition simply changes the product-sum of matrix multiplication to addition-minimization. Thus, we define this operation as \(\odot\), i.e.,

\[ A \odot B = C~~\Longleftrightarrow~~C[i,j]=\min_{1\le p \le n}\left\{A[i,p] + B[p,j]\right\} \]

Thus, we obtain

\[ L_{k+1} = L_k \odot G \]

Expanding the recurrence yields

\[ L_k = \underbrace{G \odot \ldots \odot G}_{k\text{ times}} = G^{\odot k} \]

We can still compute this using matrix fast exponentiation, as it clearly satisfies associativity. Time complexity is \(O(n^3 \log k)\).

Limited-Length Path Counting/Shortest Path

The above algorithms only apply when the number of edges is fixed. However, we can improve the algorithm to handle cases where the number of edges is less than or equal to \(k\). Specifically, consider the following problem:

Problem Description

Given an \(n\)-vertex directed graph with edge weights \(1\), and an integer \(k\), your task is to find, for each pair \((u,v)\), the number of paths from \(u\) to \(v\) with length less than or equal to \(k\) (not necessarily simple paths, i.e., vertices or edges may be traversed multiple times).

For each vertex \(v\), create a virtual vertex \(v'\) to record answers, and add edges \((v,v')\) and \((v',v')\) to the graph. Then, for a pair \((u,v)\), the number of paths from \(u\) to \(v\) with at most \(k\) edges equals the number of paths from \(u\) to \(v'\) with exactly \(k+1\) edges. This is because for any path \((p_0=u)\to p_1\to p_2 \to \dots \to p_{m-1} \to (p_m=v)\) with \(m\) edges (\(m \le k\)), there exists a corresponding path with \(k+1\) edges: \((p_0=u)\to p_1 \to p_2 \to \dots \to p_{m-1} \to (p_m=v) \to v' \to \dots \to v'\).

For finding the shortest path with at most \(k\) edges, simply add a self-loop with weight \(0\) to each vertex.

Exercises

Part of this page is translated from the blog post Кратчайшие пути фиксированной длины, количества путей фиксированной длины and its English translation Number of paths of fixed length/Shortest paths of fixed length. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用