Editorial for TSSPC Contest 1 P5 - Trick or Trail


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

The first two subtasks can be solved using Dynamic Programming. Every point (x,y) can only be reached from points (x-1,y) or (x,y-1). Therefore, the amount of paths you can take to (x,y) is equal to the paths to (x-1,y) and (x,y-1) summed together. Store the paths to (x,y) in a 2\text{D} array, and recursively sum to find the total amount of paths to (m,n)

The last subtask requires knowledge of properties of Pascal's triangle. Notice that by the above sum property, the grid follows a pattern similar to Pascal's Triangle. Another property is that the kth number in the nth row (the first row is row 0) is equal to \binom{n}{k} = \frac{n!} {(k! \ (n-k)!)}. A proof of this property can be found in the footnote. By this property, the amount of paths can be found by computing \binom{m+n}{m} = \frac{(m+n)!}{m! \ \ n!}

Thus we are presented with a new problem, how do we calculate the value effectively? Taking the factorials and then dividing would cause an overflow as n,m \leq 10^7. The solution requires taking mod after every factorial. We can perform division with mod by using the property of modular inverse. Given a \ (\text{mod } N), if \text{GCD} \ (a,N) = 1 (the numbers are coprime), then there exists an integer x < N such that ax \equiv 1 \ \ (\text{mod } N). x is the modular inverse. Dividing by a is equivalent to multiplying by x, the modular inverse. Because 10^9+7 is a prime number, (a,10^9+7) will always be coprime and there always exists a modular inverse.

One way to find the modular inverse is by looping through all values \text{mod } N. However, we have to loop through at most N operations to find the inverse. We can do one better by using Fermat's little theorem, which states that for a prime p, a^p \equiv a \ (\text{mod }p), and a^{p-1} \equiv 1 \ (\text{mod }p) if (a,p) coprime. By Fermat's little theorem, we get that a \cdot a^{10^9+5} \equiv 1 \ (\text{mod }p), which means a^{10^9+5} is the inverse of a \ (\text{mod }N).

But this is still not fast enough!!!!! We will have to do at most 10^9+5 operations if we do the exponential normally! Next, we use binary exponentiation, which is done by computing the mods of a to the exponent of a power of 2. For example if we want to compute a^{14}, we just multiply together a^8, a^4 and a^2. Here is the implementation of binary exponentiation in pseudocode:

exp = 1
x = 1000000005
while x > 0{
  if x & 1 == 1{
    exp = exp * b % 1000000007;
  }
  a = a*a % 1000000007;
  x = x >> 1;
}

return exp

Footnote To prove the Pascal triangle property, we can use Pascal's formula, which states that \binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}. Try proving that for yourself! It can also be solved by considering a set of m up operations and n right operations. The amount of paths is equal to the amount of distinct permutations of the set, which also gives \binom{m+n}{m}


Comments

There are no comments at the moment.