# PROBLEM LINK:

# DIFFICULTY

HARD

# PREREQUISITES

Elementary Number Theory, Gaussian Elimination, Dynamic Programming, Cycle Detection

# PROBLEM

A knight can make two kinds of moves from (u, v)

- (u + A
_{x}, v + A_{y}) - (u + B
_{x}, v + B_{y})

You wish to move the knight from (0, 0) to (X, Y).

You are given a set of K points P = { P_{1}, P_{2} …, P_{k}} which should not be touched by the knight.

In how many ways can the knight be moved to (X, Y) without touching any of the P points?

# EXPLANATION

First, let us forget about the fact that the answer can be very large and has to be found modulo 1000000007. We will come to this later and see how this affects the overall solution to this problem.

This problem has overall 2 cases.

### CASE I: A and B are linearly independent

Since A and B are independent, we can do a linear mapping of all the points to a space defined by the orthogonal vectors A and B.

This means that we replace each point (u, v) with (p, q) such that

`p*A`

_{x} `+ q*B`

_{x} `= u`

`p*A`

_{y} `+ q*B`

_{y} `= v`

- If (X, Y) cannot transform to an integer (x’, y’), then the number of ways to even reach (X, Y) is 0.
- If one of the points in P cannot transform to an integer (p, q), then that point will never be touched and can be ignored.

Now, we have some subset of P, lets call it Q, points which must be avoided on the way to (x’, y’). But, the step in this space, instead of A and B, is (0, 1) or (1, 0).

The number of ways of going from (0, 0) to (p, q) when step is (1, 0) or (0, 1) is

`ways(p, q) =`

^{p+q}`C`

_{p}

The case of ignoring the Q points can be solved in several ways

Approach 1. **Inclusion Exclusion**:

Sort Q, the subset of mapped forbidden points totalWays = ways(0, dest) for each subset S of Q cWays = 1 visit points in S using i = 2 to S.size, in order of appearance in Q cWays *= ways(S* - S[i-1]) sign = (S.size % 2 == 1) ? -1 : 1 totalWays += sign * cWays

Complexity: O(K*2^{K})

Approach 2. **Gaussian Elimination**:

Number of ways of reaching destination not touching any Q = Total number of ways of reaching destination - number of ways of reaching destination touching at least 1 point Q

Number of ways of reaching destination touching at least 1 point Q = `for i = 1 to Q.size, ways += x(i) * ways(i, dest)`

Where x(i) is the number of ways of reaching i’th point without touching any other point.

Let Q.size be Qc.

Now,

ways(0, j) = `for i = 1 to Qc, ways += x(i) * ways(i, j)`

for all j which are also in Q.

Thus we have Qc equations for Qc variables.

ways(0, 1) = x(1)*ways(1, 1) + x(2)*ways(2, 1) ... + x(Qc)*ways(Qc, 1) ways(0, 2) = x(1)*ways(1, 2) + x(2)*ways(2, 2) ... + x(Qc)*ways(Qc, 2) ways(0, 3) = x(1)*ways(1, 3) + x(2)*ways(2, 3) ... + x(Qc)*ways(Qc, 3) ... ways(0, Qc) = x(1)*ways(1, Qc) + x(2)*ways(2, Qc) ... + x(Qc)*ways(Qc, Qc)

This can be solved using Gaussian Elimination for `x`

in O(N^{3}) time.

Once we have `x`

we can find the number of ways of reaching (x’, y’) while touching at least 1 point Q… and hence, the number of ways of reaching (x’, y’) without touching any Q.

Approach 3: **Sorting**

By now we know that the points in Q are ordered. Thus,

Sort Q x(1) = ways(0, 1) for i = 2 to Q.size x(i) = ways(0, i) for j = 1 to i-1 x(i) -= x(j) * ways(j, i)

Thus, we have found `x`

as defined above, in O(N^{2}) time.

Thus this case is solved.

### CASE II: A and B are linearly dependent

There are a large number of corner cases to consider carefully.

- A = (0, 0) and B = (0, 0) then answer is X == (0, 0) ? -1 : 0
- If A
_{x}and B_{x}are 0 and X is not 0, the answer is 0 - If A
_{y}and B_{y}are 0 and Y is not 0, the answer is 0

Let G_{x} be the gcd of A_{x} and B_{x}

and, G_{y} be the gcd of A_{y} and B_{y}

- If X is not divisible by GX or Y is not divisible by GY, the answer is 0

We can ignore all the forbidden points which cannot be reached based on the rules above.

Now, we can scale all X co-ordinates by GX and all Y co-ordinates by GY. By all, we mean we scale only those points that are reachable.

Because of the linear dependence of A and B, we know that both the co-ordinates scale the same way when considering A or B. Thus, we can perform a DP on only the x-coordinate to find the number of ways of reaching X and we know that we will get a result for Y equivalently.

We can perform bellman-form + dynamic programming to compute the number of paths that lead up to the transformed destination - which was originally (x’, y’). We do a bellman-ford twice to catch any possible cycles.

If there is a cycle, then there are infinite number of solutions. Otherwise we have the answer by the DP.

For more clarity regarding this case, refer to the tester’s solution.

### All that number theory

Throughout this problem there is requirement of finding Binomial Coefficients modulo 1000000007.

Also, we need to perform a Gaussian Elimination in a Field of 1000000007, which basically means that all divisions performed in the gauss elimination are performed via taking multiplicative modular inverses.

Binomial coefficients can be found by precomputing the factorials modulo 1000000007 and precomputing the inverse factorials modulo 1000000007. Since the largest binomial coefficient we want is not much, we can do the following

inv = Array[10000] for i = 2 to 10000 inv* = modulo_power(i, 1000000005) fact = Array[10000] ifact = Array[10000] fact[1] = ifact[1] = 1 for i = 2 to 10000 fact* = fact[i-1] * i mod 1000000007 ifact* = ifact[i-1] * inv* mod 1000000007

Where `fact`

is the factorials modulo 1000000007 and `ifact`

is the inverse factorials modulo 1000000007.

Now,

`binomial(n,r) = fact[n]*ifact[r]*ifact[n-r] mod 1000000007`

# SETTERS SOLUTION

Can be found here (Link is broken. Will be fixing soon.)

# TESTERS SOLUTION

Can be found here