# PROBLEM LINK:

Practice

Contest

**Author:** Vasia Antoniuk

**Tester:** Sergey Kulik

**Editorialist:** Mugurel Ionut Andreica

# DIFFICULTY:

HARD

# PREREQUISITES:

Lindström–Gessel–Viennot lemma, Chinese Remainder Theorem, Binomial Coefficients, Modular inverse

# PROBLEM:

Two bunnies start at the cell **(1,1)** in a maze consisting of **N** rows and **M** columns. **C** cells contain one carrot each (all the other cells contain zero carrots). Each bunny wants to reach the cell **(N,M)** in such a way that they don't meet along the way (i.e. the only common cells of the two paths must be **(1,1)** and **(N,M)**). From a cell **(row,col)** a bunny may only move to one of the cells **(row+1,col)** or **(row,col+1)** (as long as he doesn't leave the maze). Moreover, the two paths must not contain more than **D** cells with carrots.

In how many ways can the two bunnies achieve this?

# EXPLANATION:

Let's forget about the two paths starting at **(1,1)** and ending at **(N,M)**. We can imagine that the first bunny starts at **(2,1)** and ends at **(N,M-1)**, while the second bunny starts at **(1,2)** and ends at **(N-1,M)**. With this change, the paths of the two bunnies must be completely disjoint.

The problem is an application of the [Lindström–Gessel–Viennot lemma][8]. Let's consider **(2,1)** to be the starting cell **1**, **(1,2)** starting cell **2**, **(N,M-1)** ending cell **1** and **(N-1,M)** the ending cell **2**.

Let's construct a **2x2** matrix **A**, where each element $A_{i,j}$ is a polynomial $\sum_{k=0}^{C}{a_{i,j,k}\cdot x^k}$, where $a_{i,j,k}$=the number of paths from starting cell **i** to ending cell **j** passing through **exactly k** cells containing carrots.

We then compute its determinant $D=A_{1,1}\cdot A_{2,2}-A_{1,2}\cdot A_{2,1}=\sum_{k=0}^{C}{d_k\cdot x^k}$ (note that the degree of the determinant cannot be larger than **C**, as a consequence of the lemma).

$d_k$ denotes the number of pairs of non-intersecting paths between the starting and ending cells containing exactly $k$ carrots. The final answer is $\sum_{k=0}^{D}{d_k}$ (modulo **MOD**).

Once the coefficients of the polynomials of the matrix **A** are computed, computing the answer can be done in $O(C^2)$ time (the time needed for multiplying two polynomials, without any fancy optimizations).

We will now see how to compute the values $a_{i,j,k}$. Let's consider all the **C** cells with carrots as *special*. We also mark as special the additional starting and ending cells (if they are not already special due to containing a carrot).

We will first compute the total number of paths between every pair of special cells: **CNTALL(i,j)**=the total number of paths starting at the special cell **i** and ending at the special cell **j**. Let's denote by **row(i)**, **col(i)**, **row(j)** and **col(j)** the row and column of special cell **i** and, respectively, special cell **j**. Obviously, if **row(j) <row(i)** or **col(j)<col(j)** then **CNTALL(i,j)=0**. Otherwise, $CNTALL(i,j)={{row(j)-row(i)+col(j)-col(i)}\choose {row(j)-row(i)}}$ (modulo **MOD**). We will see how to efficiently compute these binomial coefficients in a special section later.

Next we will compute the number of **direct** paths from each special cell **i** to each special cell **j** (a path is **direct** if it doesn't contain any other special cells on it). If we compute these values in the right order (i.e. in increasing order of the *row+column* sum) then this can be easily defined as:

$CNTDIRECT(i,j)=CNTALL(i,j)-\sum_{k\neq i\bigwedge k\neq j}{CNTDIRECT(i,k)\cdot CNTALL(k,j)}$.

Then, for every starting cell **S** (there are only two), we will run a dynamic programming algorithm to compute **CNTPATHS(S,i,k)**=the total number of paths starting at the starting cell **S**, ending at the special cell **i** and containing exactly **k** carrot cells. This can be computed in the same order as the **CNTDIRECT** values, as follows:

**CNTPATHS(S,sidx(S),0)=1**, if the starting cell **S** doesn't contain a carrot, **0**, otherwise.

**CNTPATHS(S,sidx(S),1)=1**, if the starting cell **S** contains a carrot, **0**, otherwise.

Here I denoted by **sidx(S)** the index in the set of special cells of the starting cell **S** ($1\leq S\leq 2$).

For $i\neq sidx(S)$ and special cell **i** doesn't contain a carrot: $CNTPATHS(S,i,k)=\sum_{j\neq i}{CNTPATHS(S,j,k)\cdot CNTDIRECT(j,i)}$.

For $i\neq sidx(S)$ and special cell **i** contains a carrot: $CNTPATHS(S,i,k)=\sum_{j\neq i}{CNTPATHS(S,j,k-1)\cdot CNTDIRECT(j,i)}$.

Computing all the **CNTDIRECT** and **CNTPATHS** values takes $O(C^3)$ time overall.

Then, assuming that ending cell **j** ($1\leq j\leq 2$) has index **eidx(j)** among the special cells we have: $a_{i,j,k}=CNTPATHS(i,eidx(j),k)$.

## Computing binomial coefficients modulo MOD

We first decompose **MOD** into prime factors: $MOD=p(1)^{e(1)}\cdot\ldots\cdot p(K)^{e(K)}$. Then we precompute for each prime factor **p(i)** all the factorials and their modular inverses, up to **N+M**. When computing a factorial we exclude all the factors equal to **p(i)**. To be more precise, we define **fact(i,0)=factinv(i,0)=1** and **pcnt(i,0)=0**. Then, for $1\leq j\leq N+M$, we write **j** as $p(i)^{q(i,j)}\cdot x$. We set **pcnt(i,j)=pcnt(i,j-1)+q(i,j)** and $fact(i,j)=fact(i,j-1)\cdot x$ (modulo $p(i)^{e(i)}$). We also compute **factinv(i,j)** as the modular inverse of **fact(i,j)** (modulo $p(i)^{e(i)}$). There are smart techniques for efficiently computing factorials and their inverses quickly, but in this case it's enough to compute each inverse inedependently (e.g. by using the Extended Euclidean Algorithm ). This way the total precomputation time is **O((N+M)xlog(MOD))**.

Once all these values are computed (once for each test case), let's see how we can compute $A\choose B$ (modulo **MOD**).

We will compute $r(i)={A\choose B}$ (modulo $p(i)^{e(i)})$ ($1\leq i\leq K$). Then we will find the remainder modulo **MOD** by combining these **K** remainders using the [Chinese Remainder Theorem][9].

In order to compute $r(i)$ we will use the fact that ${A\choose B}=\frac{A!}{(A-B)!\cdot B!}$. We will first compute **DIF=pcnt(i,A)-pcnt(A-B)-pcnt(B)**. **DIF** is the exponent at which the prime factor **p(i)** appears in the binomial coefficient. if $DIF\geq e(i)$ then $r(i)=0$ (because the binomial coefficient is divisible by $p(i)^e(i)$). Otherwise $r(i)=p(i)^{DIF}\cdot fact(i,A)\cdot factinv(i,A-B)\cdot factinv(B)$ (modulo $p(i)^{e(i)}$). Computing $p^{DIF}$ can be done either in logarithmic time using fast modular exponentiation, or we can precompute all the needed powers (since $DIF\leq e(i)$).

Computing one binomial coefficient can, thus, be done in **O(Kxlog(K))** time (where **K** is the number of distinct prime factors of **MOD**) and we need to compute $O(C^2)$ binomial coefficients.

## Overall time complexity: $O(C^3+C^2\cdot K\cdot log(MOD)+(N+M)\cdot K\cdot log(MOD))$.

# AUTHOR'S, TESTER'S AND EDITORIALIST'S SOLUTIONS:

Author's solution can be found here.

Tester's solution can be found here.

Editorialist's solution can be found here.