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.
- 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
- 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.
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.
After performing each query, print a single line containing one integer ― the number of ways to form a curious matrix, modulo 109+7.
p is a prime number
- 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
2 6 5
1 1 3
1 2 1
2 1 1
2 2 4
1 2 1
2 2 4
- 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.
January Long Challenge 2021
- Chef and Division 3 DIVTHREE SOLUTION Code Chef
- Encoded String DECODEIT SOLUTION Code Chef
- Point Of Impact BILLRD SOLUTION Code Chef
- Fair Elections FAIRELCT SOLUTION Code Chef
- Watching CPL WIPL SOLUTION Code Chef
- Chef and Ants ANTSCHEF SOLUTION Code Chef
- Blackjack BLKJK SOLUTION Code Chef
- And-Or Game ORAND SOLUTION Code Chef
- Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef
- Expected Number of SCCs RCTEXSCC SOLUTION Code Chef
- Curious Matrix CURMAT SOLUTION Code Chef
- Cool Subsets COOLSBST SOLUTION Code Chef
- Sequence Creation ARCRT SOLUTION Code Chef
- Greedy Students GRDSTD SOLUTION Code Chef