Curious Matrix

[paliwalharsh]

Issue Id you have worked upon -

365

Briefly explain your program logic -

It can be shown that the 2nd2nd curious condition is equivalent to the matrix having rank 11 with respect to modulo pp. In a rank 11 matrix, each row is a multiple of every other row and each column is a multiple of every other column . Hence there is a cyclic dependency between the cells, i.e., 1 \leq a,b,c,d \leq N1≤a,b,c,d≤N, M{a,b}*M{c,d}M a,b ​ ∗M c,d ​ \equiv≡ M{a,d}*M{c,b}M a,d ​ ∗M c,b ​ modmod pp, thus if any 3 of these cells have values in them, the 4th cell necesaarily needs to have a particular value to obey the rank 11 matrix condition . There are actually a total of 2N-12N−1 individual cells whose values independently can determine the values to be filled in all other cells for the matrix to have rank 11 . Intuitively just consider the 1st1st row and 1st1st column filled, a total 2N-12N−1 cells . These are actually the independent constants in a graph, the count of free constants available decide the count of ways to form a curious matrix, (p-1)^f(p−1) f , ff being the current count of free constants. The problem can be modelled into a graph problem. Consider 2N2N nodes in the graph, each node representative of a row or a column, nodes 11 to NN for the rows and N+1N+1 to 2N2N for the columns . For every filled cell M_{x, y}M x,y ​ containing value vv, consider a directed edge from node xx to node y+Ny+N with weight vv and another directed edge from node y+Ny+N to node xx with weight 1/v1/v (inverse of vv w.r.t prime pp) . Now to obey the rank 11 matrix condition, the products of all edge weights in a cycle in the graphymust be 11 . The count of free constants is decided by the number of disconnected components in graph subtracted by 11. The addition query alone could have been handled in O(log N)O(logN) by a DSU. However to handle deletion queries, dynamic connectivity comes into play .

Screenshots(Attach 2 screenshots of your own input and output) -

Attach here

Checklist:

Eg - If your code follows the below guidelines. Kindly change [] to [x]

All the conditions should be fulfilled for considering your code for merging -

• [x] I have mentioned the question as comment in my solution file.
  

• [x] My code follows the guidelines of this project.
  

• [x] I have performed a self-review of my own code.
  

• [x] I have commented on my code.
  

• [x] My code gives the correct output.
  

• [x] I confirm that I have not copied the code from anywhere. In case its found that I have copied even after successful merge then I can be banned from the repository and hacktoberfest.
  

• [x] I affirm that I strictly follow contributing guidelines and code of conduct.

[SarthakKeshari]

@paliwalharsh, This PR will be marked as invalid and be closed by 13/10/2021(6PM). Kindly respond by either closing it or making the required changes.

[paliwalharsh]

Update CuriousMatrix.cpp with important comments for easy understanding of the learners.

[paliwalharsh]

updated, done by mistake