# How to solve this dynamic programming puzzle on matrix?

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

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

• Which approaches have you tried? Where did you get stuck? I guess with N and M describe the dimension of the matrix. oh should clarify this in your post. – Daniel Oct 10 at 10:13
• This appears to be taken from an ongoing coding contest: codechef.com/OCT19A/problems/JIIT. Parts of this appear to be copied word-for-word from that source. Plagiarism is not cool -- we require people to credit the source of all copied material. – D.W. Oct 11 at 18:42
• – D.W. Oct 11 at 18:51