Editorial for TLE '17 Contest 4 P5 - Pascal's Tree


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.

Author: d

For the first subtask, it is enough to generate the N^{th} row of Pascal's Triangle, then print out the elements of the row modulo M. Alternatively, you can use the formula for the combination, and then print this number modulo M. The formula for the combination is given below:

\displaystyle \dbinom{n}{k}=\begin{cases} \dfrac{n!}{k! \times (n-k)!} & \text{if } 0 \le k \le n \\ 0 & \text{if } k < 0 \text{ or } k > n \end{cases}

\displaystyle n!=\begin{cases} 1 & \text{if } n = 0 \\ n \times (n-1)! & \text{if } n \ge 1 \end{cases}

Time Complexity: Slower than \mathcal{O}(N^2)

For the second subtask, it is enough to generate the N^{th} row of Pascal's Triangle by storing the elements of each previous row modulo M. Alternatively, you can use the formula for the combination in a data type that supports arbitrary-precision integers, such as Java's BigInteger or Python's normal integer, then print this number modulo M.

Time Complexity: \mathcal{O}(N^2)

For the third subtask, we first notice that M is prime and M>N. This means that no number in the N^{th} row is divisible by M. Since M is prime, we can use Fermat's Little Theorem to get the multiplicative inverse. If x is not divisible by M, then x^{10^8+5} \times x \equiv 1 \pmod{10^8+7}, and we have that x^{10^8+5} is the multiplicative inverse of x.

Why do we need the multiplicative inverse? Suppose that you have A \times x \times B, you know the value of x, and you want to find A \times B. You would compute (A \times x \times B) \times x^{10^8+5} \equiv (A \times B) \times (x \times x^{10^8+5}) \equiv A \times B \pmod{10^8+7}. To divide by x, you instead multiply by x^{10^8+5}.

Next, suppose that we have already computed 0!, 1!, \dots, N! modulo M and we want to find \dbinom{N}{k} \bmod M. We can instead find:

\displaystyle \left(N! \times (k!)^{10^8+5} \times ((N-k)!)^{10^8+5}\right) \bmod M

The time complexity of this computation is \mathcal{O}(\log M), and you should repeat this computation N+1 times.

Make sure that 64-bit integers are used, and no overflows will occur.

Time Complexity: \mathcal{O}(N \log M)

The fourth subtask is a distraction. This time, we could have M<N, and this would result in some elements being divisible by M. I have found a few online articles that point to Lucas's Theorem, which could be helpful.


For the fifth subtask, we will first look at the relationship between two adjacent combinations.

\displaystyle \dbinom{N}{i-1} \times \frac{N-i+1}{i} = \dbinom{N}{i}

The proof of this relationship is very boring. I recommend that you try to prove it! Hint: expand everything.

A combination can always be factored as a product of prime numbers. Also, two adjacent combinations share many of the same prime factors. We want to create a multiset that supports these 3 operations:

  • Insert a prime number
  • Erase an existing number in the multiset
  • Calculate the product of the numbers in the multiset modulo M

This data structure is easiest to implement as a segment tree, although a BBST should also work fine too.

In total, around \mathcal{O}(N \log N) prime numbers will be inserted/erased in the data structure (there is probably a better bound, but this is good enough). Each insert/erase operation will take \mathcal{O}(\log N) time to update the product (this time complexity can be improved).

Time Complexity: \mathcal{O}(N \log^2 N), or slightly better

Note 1: If you have trouble passing this problem, you may find \dbinom{N}{i} = \dbinom{N}{N-i} useful. In the best case, this optimization will cut your runtime in half.

Note 2: Some programmers have found a way to solve this problem using FFT. I may include an analysis of this approach later.


Comments


  • 1
    kedrist  commented on Dec. 24, 2017, 1:34 p.m.

    It can also be done using CRT. Check my solution for more details.