PROBLEM LINK:
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.