Determinant Construction (Hard Version)

The useful way to look at the matrix is not as 2500 independent cells. That is a trap with fluorescent lighting. We only need one thin band.

Continuant Recurrence

Let $A_k$ be the determinant of the top-left $k$ by $k$ prefix, and set $A_0=1$. Build a tridiagonal matrix with $M_{i,i}=1$, $M_{i,i-1}=1$ for $i>1$, and $M_{i-1,i}=s_i$, where $s_i$ is either $1$ or $-1$.

For a tridiagonal matrix, expanding the last row/column gives

$A_i=A_{i-1}-s_iA_{i-2}$.

So:

• if $s_i=-1$, then $A_i=A_{i-1}+A_{i-2}$;
• if $s_i=1$, then $A_i=A_{i-1}-A_{i-2}$.

The row/column condition is basically free now: every internal row and column has at most three non-zero entries, and the two ends have at most two.

Start with $A_0=1$ and $A_1=1$. Choosing the first superdiagonal as $-1$ gives $A_2=2$. Therefore, if we can create a sequence

$1,2,...,x$

where every new term is the previous term plus or minus the term before it, the matrix follows immediately.

Reverse Construction

Suppose the last two sequence values are $a$ and $b$. The value before them must be $|a-b|$, because forward we had either $a=b+c$ or $a=b-c$.

So one reverse step is

$(a,b) -> (b,|a-b|)$.

If this process reaches $(2,1)`, reversing the collected values gives a valid sequence starting from$1,2$and ending at$x$.

This process preserves gcd, so choosing $b$ with $gcd(x,b)>1$ is dead on arrival. The helper work(x,b) runs this reverse process and returns the resulting sequence length, or infinity if it does not reach gcd $1$ within the limit.

Finding A Good Previous Value

A random previous value is cute for the easy version, but here $n<=50$ and $t$ can be large, so random poking is playing with fire.

Fibonacci pairs are the clean shape we want. Let $F_0=F_1=1$. If

$x=pF_i+qF_{i-1}$,

try

$b=pF_{i-1}+qF_{i-2}$.

Then the reverse process starts as

$(pF_i+qF_{i-1}, pF_{i-1}+qF_{i-2}) -> (pF_{i-1}+qF_{i-2}, pF_{i-2}+qF_{i-3}) -> ...$.

So the large number shrinks Fibonacci-style instead of by awful one-by-one subtraction.

For each Fibonacci index $i$, consecutive Fibonacci numbers are coprime, so the equation $pF_i+qF_{i-1}=x$ is solved with extended gcd. All non-negative solutions are checked, and the candidate $b$ is accepted only if work(x,b)<=50. That final check matters: the code does not trust the heuristic blindly. For every $x<=10^7$, this Fibonacci-guided finite search finds a valid $b$.

Building The Matrix

After $b$ is found, run the reverse process and store the values. Then build forward from the $1$ by $1$ matrix $[1]$.

When the next target value is larger than the current determinant, set the new superdiagonal entry to $-1$, making the recurrence add the previous determinant. Otherwise set it to $1$, making the recurrence subtract the previous determinant.

At the end, the full determinant is $x$. The side length is exactly the sequence length, which work already checked to be at most $50$. For $x=0$, just output the $1$ by $1$ zero matrix.

Correctness Proof

Lemma 1. For the constructed tridiagonal matrix, the prefix determinants satisfy $A_i=A_{i-1}-s_iA_{i-2}$.

Proof. This is the standard determinant recurrence for tridiagonal matrices. The diagonal entry is $1$, the subdiagonal entry is $1$, and the superdiagonal entry is $s_i$, so the last two terms contribute exactly $A_{i-1}-s_iA_{i-2}$.

Lemma 2. Given a valid sequence where every term is the sum or difference of the previous two, the forward construction makes the prefix determinants equal to that sequence.

Proof. Start with determinant $1$. For each next target, choose $s_i=-1$ for addition and $s_i=1$ for subtraction. By Lemma 1, the next prefix determinant becomes exactly the chosen next sequence value.

Lemma 3. If the reverse process from $(x,b)$ reaches $(2,1)$ in at most $50$ total states, then reversing the collected values gives a valid sequence ending at $x$.

Proof. Each reverse step replaces $(a,b)$ with $(b,|a-b|)`, which is exactly undoing one forward sum/difference step. Reversing the list therefore restores a sequence where every term is formed legally from the previous two. Since it ends at$(x,b)$, the final determinant target is$x$.

Theorem. The algorithm outputs a valid matrix for every test case.

Proof. For $x=0$ and $x=1$, the one-cell matrices are immediate. Otherwise, findPrev returns a value $b$ whose reverse process has length at most $50$ and reaches $(2,1)`. By Lemma 3, this gives a valid determinant sequence ending at$x$. By Lemma 2, the matrix built from that sequence has determinant$x$. The matrix is tridiagonal, so every row and column has at most three non-zero entries, and all entries are in${-1,0,1}$. Thus all required conditions hold.

Complexity

Fibonacci indices only go up to about $35$ for $10^7$, and each candidate check takes at most $51$ reverse steps. Outputting the matrix costs $O(50^2)$ per test case, which dominates the boring part.