Determinant Construction (Easy Version)

Key idea: stop trying to handcraft determinant values directly. A determinant expansion already sums over permutations. A permutation is the same as choosing exactly one outgoing and one incoming edge at every vertex, i.e. a cycle cover. So we build a sparse directed graph where cycle covers are exactly source-to-sink paths. Then the determinant counts those paths. Linear algebra puts on a fake mustache and becomes DP.

From paths to a matrix Suppose we have a DAG $G$ with source $1$, sink $n$, exactly $x$ paths from source to sink, indegree <= 2, outdegree <= 2, and no edges entering the source. Build matrix $M$ like this:

• for every DAG edge $i -> j$, set $M_{i,j}=-1$;
• for every internal vertex $2..n-1$, set $M_{i,i}=1$;
• set $M_{n,1}=1$;
• everything else is $0$.

Now look at any nonzero term in the determinant expansion. Row $n$ has only one nonzero, so it must choose edge $n -> 1$. Since the graph is acyclic, the only way to complete a non-self-loop cycle through this edge is to choose a directed path from $1$ to $n$ in the DAG. Every vertex not on that path just takes its self-loop. So cycle covers and source-to-sink paths are in bijection.

The signs also behave, which is the part that looks suspicious until you check it. If the path has $l$ DAG edges, the big cycle has length $l+1$. The determinant sign of that cycle is $(-1)^l$. The product of edge weights along the path is also $(-1)^l$, because every DAG edge has weight $-1$ and the closing edge has weight $1$. Multiply them: $1$. Self-loops add no drama. Therefore every path contributes exactly $+1$, so the determinant of $M$ is exactly the number of paths in $G$.

The row and column limits are also handled. A row gets at most two DAG outgoing edges plus maybe one self-loop. A column gets at most two DAG incoming edges plus maybe one self-loop. The sink has no self-loop, and the source only gets the closing edge. So the matrix has at most 3 nonzero entries in every row and column.

Building a DAG with exactly $x$ paths Since $x <= 10^7$ and $3^15 > 10^7$, base 3 is plenty.

Use 15 identical gadgets. If a gadget starts at vertex $v$, add these edges:

$v -> v+1 -> v+2 -> v+3 -> v+4$, plus $v+1 -> v+3$ and $v+2 -> v+4$.

If there are $p$ paths reaching $v$, then there are $2p$ paths reaching $v+3$ and $3p$ paths reaching $v+4$. The next gadget starts at $v+4$, so gadget $i$ has a start vertex with $3^i$ paths and a side vertex with $2*3^i$ paths.

Now write $x$ in base 3. For trit $d_i$:

• if $d_i=1$, branch from the start vertex of gadget $i$;
• if $d_i=2$, branch from the side vertex $v+3$ of gadget $i$;
• if $d_i=0$, do nothing.

All branches enter a separate answer chain. When the current chain tail is $t$, a selected branch adds edges branch_point -> t and t -> t+1, then the tail becomes $t+1$. Each selected branch has exactly one way to continue to the final sink, so the total number of source-to-sink paths is the sum of the selected branch counts, i.e. exactly the base-3 value $x$.

Node count: the 15 gadgets use $1+4*15=61$ vertices. We add one initial answer-chain vertex and at most one more vertex for each nonzero trit, so at most $61+1+15=77 <= 80$. Degree count stays <= 2 in the DAG: a branch only adds one extra outgoing edge to a vertex that previously had one outgoing edge, and answer-chain vertices have one outgoing edge and at most two incoming edges.

For $x=0$, output the 1 by 1 zero matrix. Done, no need to make zero look fancy.

Complexity is tiny: $O(80^2)$ output work per test case.