Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
- Subtracting
~1~ from each square allows us to think of the problem in terms of modulo-
~p~ arithmetic.
- Since addition is commutative in modulo-~p~ arithmetic, we can see that the order in which we select squares doesn't matter.
- Let
~x_{i,j}~ denote the number of times square 
~(i, j)~ is selected, and let 
~v_{i,j}~ denote the initial value of square ~(i, j)~. Then we want:
$$\displaystyle v_{i,j} + \left(\sum_{k=1}^n x_{k,j} + \sum_{k=1}^m x_{i,k} - x_{i,j}\right) \equiv p-1 \pmod p$$
- Assume for a moment that
~x_{i,j} \in \mathbb R~ and that we wanted (for some 
~K \in \mathbb R~):
$$\displaystyle v_{i,j} + \left(\sum_{k=1}^n x_{k,j} + \sum_{k=1}^m x_{i,k} - x_{i,j}\right) = K$$
- Then we have a system of
~n \times m~ linear equations in ~n \times m~ variables, which we could solve using Gaussian elimination.
- It turns out that Gaussian elimination works over any field (which includes modulo-~p~ arithmetic), so we can use the same method to solve our problem! Just perform all operations of the Gaussian elimination modulo ~p~.
- Performing a division
~a/b~ modulo ~p~ is the same as multiplying 
~a~ by the modular multiplicative inverse of 
~b~ modulo ~p~, which can be computed with the Euclidean algorithm.
- All ~x_{i,j}~ can be taken modulo ~p~, which means that, if there is a solution, it will not use more moves than allowed by the problem statement.
- Some care has to be taken when there are multiple solutions, or no solutions, as described by the Rouché-Capelli theorem. For the case of multiple solutions, it suffices to set all free variables to zero.
- Time complexity is
~\mathcal O(n^3 m^3)~.
Comments