Curious Matrix CURMAT SOLUTION Code Chef

Curious Matrix CURMAT SOLUTION Code Chef

You are given a prime p and a matrix M with N rows (numbered 1 through N) and N columns (numbered 1 through N). For each row r and column c, the cell in row r and column c can either be empty or contain an integer Mr,c. Initially, all cells are empty.
Curious Matrix CURMAT SOLUTION
Now you should process Q queries. In each query, you are given integers x, y and v and you should do the following:

 

If the cell (x,y) is empty before this query, put the value v in it, i.e. set Mx,y to v.
Otherwise, i.e. if the cell (x,y) is not empty, make this cell empty again. It is guaranteed that in such a case, Mx,y=v before this query; v is provided for convenience.Curious Matrix CURMAT SOLUTION
Afterwards, Chef wants you to find the number of ways to fill all empty cells with (not necessarily the same) integers in such a way that the resulting matrix is curious. Since this number may be large, compute it modulo 109+7.Curious Matrix CURMAT SOLUTION
In particular, when there are no empty cells in the matrix, the answer is 1 if the matrix is curious or 0 if it is not curious.
 
In a curious matrix:
Each cell contains an integer between 1 and p−1 inclusive.
For each non-trivial square submatrix A of M (a submatrix containing more than one cell), its determinant |A| is a multiple of p.
For example, consider the following matrix.
  • A=⎡⎣⎢122244122⎤⎦⎥
  • This matrix is curious. For the prime p=5, each of the elements of the matrix is in the range [1,p−1]. Also, the determinant of each non-trivial square submatrix (there are five of them) is a multiple of the given prime ― for example, the determinant of the whole matrix is 0.Curious Matrix CURMAT SOLUTION
  • B=[3114]
  • The above matrix is not a curious matrix for p=5, since the determinant of the only non-trivial square submatrix (which is the whole matrix) is 11, not a multiple of p.
Input
The first line of the input contains three space-separated integers N, Q and p.
Q lines follow. Each of these lines contains three space-separated integers x, y and v describing a query.
Output
After performing each query, print a single line containing one integer ― the number of ways to form a curious matrix, modulo 109+7.
 
Constraints
2≤N≤105
1≤Q≤105
2≤p≤998,244,353
p is a prime number
1≤x,y≤N
1≤v≤p−1
Subtasks
  • Subtask #1 (20 points): 1≤N,Q≤300
  • Subtask #2 (20 points): no two queries affect the same cell, i.e. the pairs (x,y) for all queries are pairwise distinct
  • Subtask #3 (20 points): after each query, there is at least one way to construct a curious matrix
  • Subtask #4 (40 points): original constraints
Example Input
2 6 5
1 1 3
1 2 1
2 1 1
2 2 4
1 2 1
2 2 4
Example Output
16
4
1
0
1
4
Explanation
  • The only non-trivial square submatrix here is the whole matrix.
  • In the 4-th query, the matrix is completely filled, but it is not curious for p=5, so the answer is 0.
  • After the 5-th query, there are 3 filled cells: (1,1)→3, (2,1)→1 and (2,2)→4. The cell (1,2) is empty and if we want the determinant of the matrix to be divisible by p=5, we have to put 2 in this cell. Then the determinant is 3⋅4−1⋅2=10.

4 thoughts on “Curious Matrix CURMAT SOLUTION Code Chef”

Leave a Comment

close
error: Content is protected !!