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}$
