0
$\begingroup$

We are given 4 integers N,M ,Q and Z.

Initially,the matrix has all zeroes in it.

We have to perform Q operations on the matrix.

In each operation, any cell of the matrix can be selected(same cell can be selected multiple times) .

Once a cell (x,y) is selected, you have to add '1' to all the elements of row 'x' and column 'y' .

After all the operations are done , there should be exactly "Z" numbers in the matrix which are odd.

How many sequences of Q-operations are possible for given $N,M,Q,Z$

Example:-

N=2,M=2,Q=2,Z=0

Answer:- 8

If we start by choosing the cell (1,1), the matrix becomes

2 1

1 0

Now we have two options ― we can choose either even-valued cell. If we choose (1,1) again, the matrix becomes

4 2

2 0

If we choose (2,2) instead, it becomes

2 2

2 2

For each of the other three possible initial cells, there are also two cells we can choose in the second operation, which is 4⋅2=8 ways in total.

$N$ and $M$ are dimensions of the matrix.

What have I tried:-

Number of ways to select 'Q' distinct points on a matrix:-

$^{N*M}C_{Q}$

Number of ways to select 'Q' points on a matrix with repetition allowed:-

$^{N*M+Q}C_{Q}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.