Problem J
Permanent
The permanent of a square matrix is similar to the determinant, except that it does not alternate signs. Instead of subtracting terms, all terms in the expansion are added.
Formally, for a square matrix $A$ with $n$ rows and $n$ columns, let $a_{i,j}$ denote the entry in row $i$, column $j$. The minor of row $i$ and column $j$, denoted $A_{i,j}$, is the $(n-1) \times (n-1)$ matrix obtained by removing row $i$ and column $j$ from $A$.
The permanent of $A$ is defined recursively for $n \ge 2$ as:
\[ \text{perm}(A) = \sum _{j=1}^{n} a_{r,j} \cdot \text{perm}(A_{r,j}), \]where $r$ is any row between $1$ and $n$ (the result is the same regardless of the row chosen).
For a $1 \times 1$ matrix, the permanent is simply the value of its single element.
Example: The permanent of
\[ \begin{bmatrix} 2 & 3 \\ 5 & 7 \end{bmatrix} \]is $2 \times 7 + 3 \times 5 = 29$.
Input
-
A single integer $n$ ($1 \le n \le 10$) — the size of the square matrix.
-
$n$ lines, each containing $n$ space-separated integers. The $j$-th integer on the $i$-th line is $a_{i,j}$, the entry in row $i$, column $j$ of the matrix. Each value satisfies $|a_{i,j}| \le 10$.
Output
Print a single integer — the permanent of the input matrix.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 2 3 5 7 |
29 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 1 2 3 4 5 6 7 8 9 |
450 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 -1 2 -3 -2 4 5 6 7 -8 0 3 1 -4 -5 8 -6 |
-1471 |
