P16443 [XJTUPC 2026] Matrix Decomposition

You are given an $n \times n$ non-negative integer matrix $B$. You need to construct an $n \times n$ non-negative integer matrix $A$ such that: - $A + A^\mathsf{T} = B$. Here, $A^\mathsf{T}$ denotes the transpose of $A$, which is the matrix obtained by swapping its rows and columns (the element in row $i$ and column $j$ of $A$ is located in row $j$ and column $i$ of $A^\mathsf{T}$). - For any $i = 1,2,\cdots , n$, we have $$\left\lfloor \frac{1}{2}\sum\limits_{j=1}^n B_{ij} \right\rfloor \le \sum\limits_{j=1}^n A_{ij} \le \left\lceil \frac{1}{2}\sum\limits_{j=1}^n B_{ij} \right\rceil$$ - For any $j = 1,2,\cdots , n$, we have $$\left\lfloor \frac{1}{2}\sum\limits_{i=1}^n B_{ij}\right\rfloor \le \sum\limits_{i=1}^n A_{ij} \le \left\lceil \frac{1}{2}\sum\limits_{i=1}^n B_{ij} \right\rceil$$ Or report that there is no solution. Here, $A_{ij}$ is the element in row $i$ and column $j$ of matrix $A$, and $B_{ij}$ is the element in row $i$ and column $j$ of matrix $B$. If there are multiple solutions, you may output any one.

**This problem contains multiple test cases**. The first line contains a positive integer $T$ ($1 \leq T \leq 1000$), which is the number of test cases. Next are the descriptions of the $T$ test cases. The first line of each test case contains an integer $n$ ($1 \le n \le 2200$), which is the size of the matrix. The next $n$ lines each contain $n$ integers separated by spaces, describing matrix $B$. The $j$-th integer in the $i$-th line is $B_{ij}$ ($0 \leq B_{ij} \leq 10^9$). It is guaranteed that the sum of $n^2$ over all test cases does not exceed $5 \times 10^6$.

For each test case, if there is no solution, output one line containing only the string $\tt{No}$. Otherwise, output $n + 1$ lines, where: - The first line contains the string $\tt{Yes}$. - The next $n$ lines each contain $n$ integers separated by spaces, describing the matrix $A$. The $j$-th integer in the $i$-th line is $A_{ij}$ ($0 \leq A_{ij} \leq 10^9$). If there are multiple solutions, you may output any one. The answer is case-insensitive. For example, $\tt{yEs}$, $\tt{Yes}$, $\tt{yes}$, and $\tt{YES}$ will all be considered as $\tt{Yes}$.

Translated by ChatGPT 5