### PROBLEM LINK:

**Author:** Anudeep Nekkanti

**Tester:** Minako Kojima

**Editorialist:** Lalit Kundu

### DIFFICULTY:

EASY-MEDIUM

### PRE-REQUISITES:

Mathematics, Probability

### PROBLEM:

Consider an **N** by **M** grid. Rows are numbered **1** to **N**, from top to bottom. Columns are numbered **1** to **M**, from left to right. You are initially at cell (1, 1) and want to go to cell (**N, M**). From any cell you can move to the cell below it or to the cell right to it. You should never go out of the grid. At any point you should consider all the possibilities of movement with equal probability

Let P[i][j] be the probability of visiting cell (i, j). You need to calculate the sum of P[i][j] for **1** ≤ **i** ≤ **N**, **1** ≤ **i** ≤ **M**.

### QUICK EXPLANATION:

Answer is **N+M-1** because after sum of probabilities of all cells in same diagonal is 1.

### EXPLANATION:

#### APPROACH 1:

Consider that you are cell (1, 1).

After 1 step, what all cells we can reach?

(0, 1) and (1, 0).

After 2 steps, what all cells we can reach?

(0, 2), (1, 1)and (2, 0).

After 3 steps, what all cells we can reach?

(0, 3), (2, 1), (1, 2)and (0, 3).

and so on.

If we go on writing like that, we end up writing the diagonals from left top to right bottom and each cell being covered once.

For example, this table shows required steps for reaching each cell.

```
0 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
```

Now, probability at (0,0) is 1. After we take a step, the sum of probabilities of positions a step away from (0,0) will be 1 because it is clear, no matter how we move we will be one step further, we’ll reach the next diagonal. So the sum of probabilities remains 1.

Therefore, sum of probabilities in each diagonal is 1. And there are a total of **N + M - 1** diagonals.

So our answer in **N + M - 1**.

#### APPROACH 2(slow, wouldn’t pass):

Consider **F1(x, y)** to be the number of ways to reach cell **(x, y)** from cell **(0, 0)**.

Consider **F2(x, y)** to be the number of ways to reach cell **(N-1, M-1)** from cell **(x, y)**.

We know that **F1(x, y) = (x + y)! (x! * y!)**, where **N!** denotes **1*2*3…N**.

So, in a similar way **F2(x, y) = F1(n - x - 1, m - y - 1)**.

Now, what’s the probability of visiting cell **(x, y)**. It’s equal to number of paths that pass through it divided by total number of paths.

So, P(x, y) = \frac{(F1(x, y) F2(x, y))}{F1(n-1, m-1)}.

So, we precalculate array **fact**, where **fact[i]** stores **log2(1*2*3…i)**. We store our calculation **log2** because otherwise we’ll have to store numbers as large as 1000 factorial!

Now, F1(x, y) = 2^{fact[x + y] - fact[x] - fact[y]}.

Since we have all values in powers of 2, we can use exponent arithmetic.

Complexity: **O(N*M)**.