Let $p_1$ be the identity permutation and $p_2$ be (1,2) cycle.
Both must achieve the same sum but they differ in two terms:
$p_1$ is A[1][1] + A[2][2] = c
$p_2$ is A[1][2] + A[2][1] = c
then A[1][1] + A[2][2] = A[1][2] + A[2][1]
A[1][1] - A[1][2] = A[2][1] - A[2][2]
A[1][1] - A[1][2] = A[2][1] - A[2][2]

So the coordinate-wise difference between all numbers in two columns/rows remains the same.
This is enough for the subtasks with A_{i, j} \neq 1. This should give the intuition that there is a one-to-many relation between 
cute matricies and pairs (X, Y) of n-dimensional vectors with no negative coordinates. It is possible that different (X_1, Y_1) \neq (X_2, Y_2) yield
the same cute matrix. (Proof is left as an exercise.)
More specifically it must be true that A[i][j] = X[i] + Y[j] for all suitable i, j.

Subtasks 6 and 7 give us the constant sum \sum_{i=1}^n A_{i,i}. The task remains to find how many ways are there to 
fill the rest of the -1s. In terms of (X, Y) that means that we have fixed X[i] + Y[i] = A[i][i].
There are \prod_{i=1}^n (A[i][i] + 1) ways to do so, but we have not accounted for duplicating cute matricies (this is not necessary in subtask 6).
To reduce subtask 7 to subtask 6 we must notice that there were no duplicates in the earlier subtask, since one X[1] + Y[1] = 0 is forced or equivalently
X[1] = Y[1] = 0 is forced. If for some (X, Y), min(X) \geq 1, there must be another (X', Y') such that it yields the same matrix but min(X)=0
It is enough to subtract the overcounted matricies which are given by \prod_{i=1}^n A[i][i] (imagine that a 1 is given to all coordinates in X before anything else is done). 

(Almost) finally, let's look at the subtasks with A_{i,j}=0 for some suitable {i,j}. Similarly to subtask 6 this forces a unique representation of every matrix.
It is somewhat common in matrix problems to work with a bipartite graph with nodes
the rows/columns and edges -- the cells in the matrix. A_{i, j} \neq 0 -> X[i] + Y[j] = A_{i, j}. Fixing X[i] will give us the value of Y[j] and knowing the value of Y[j]
can give us the value of some other X[i]s and so on. In a way, fixing a single value in a connected component in our bipartite graph, solves the whole component.
Brute forcing a single node in a component gets subtask 9 and only checking for contradictions gets subtask 10.

Finally, we must deal with the overcounting problem in a way similar to how we transitioned from subtask 6 to 7.