I could only get 30 pts with dp i have seen other ppl submission but dont know the logic they are using
You need to find the number of cells that can be independently changed. All the other cells are determined once you find those. Because you can choose those x cells, the number of possibilities is 2^x.
Make each cell a variable and using the number system integers mod 2, you can represent all the constraints as a linear system of equations. Each equation is essentially an xor operation.
The system equations form a matrix. You can then solve using Gaussian elimination to find the rank of that matrix, which gives the number of independent equations in that system. If there are n cells, than the number of independent variables is x = n - rank(matrix). Compute 2^x mod (10^9+7).
3 Likes
I also passed it that way but won’t the complexity of this be O(n^3). Even with bitset optimisation it will be 900^3/64 and there are 100 testcases. Is my assumption correct or am I missing something here ??