Contest Duration: - (local time) (100 minutes) Back to Home

## Ex - Fill Triangle Editorial by en_translator

Before starting the editorial on the problem, we will first pick up on some of the properties of binomial coefficients $$\binom{n}{r} \bmod p$$.

#### $$\binom{p^k}{n} \bmod{p}$$

For all primes $$p$$ and all positive integers $$k$$, it holds that:

$(x+1)^{p^k} \equiv x^{p^k} + 1 \pmod{p}.$

In other words, for all integers $$i$$ $$(0 \leq i \leq p^k)$$, it holds that:

$\binom{p^k}{n} \bmod p = \begin{cases} 1 & n = 0, p^k \\ 0 & \mathrm{otherwise}. \end{cases}$

(Proof) We will prove it by induction.

If $$k=1$$, obviously $$\binom{p}{0}=\binom{p}{p}=1$$. If $$1 \leq n \leq p-1$$,

$\binom{p}{n} = \frac{p(p-1) \cdots (p-n+1) }{n!},$

whose denominator is indivisible by $$p$$, so $$\binom{p}{n} \equiv 0 \pmod{p}$$.

Assume that the statement is true for $$k = m$$ such that $$m \geq 1$$. Then, we can apply the assumption for $$k=m$$ to $$k = m+1$$ as

$(x+1)^{p^{m+1}}\equiv ((x+1)^{p^m})^p\equiv (x^{p^m} + 1)^p \pmod{p},$

so it can be proven in the same way to $$k=1$$. (End of proof)

There is an advanced theorem called Kummer’s theorem that enables us to find how many times $$p$$ divides $$\binom{N}{k}$$.

#### Lucas’s theorem

When non-negative integers $$n,k$$ are expressed in base $$p$$ as

$n = a_r p^r + \cdots + a_1 p + a_0,$

$k = b_r p^r + \cdots + b_1 p + b_0,$

the following equation holds:

$\binom{n}{k} \equiv \prod_{i=0}^r \binom{a_i}{b_i} \pmod p.$

This can be justified by transforming $$(1+x)^n$$ using the theorem we have shown above:

\begin{aligned} &[x^k] (1+x)^n \\ &\equiv [x^k]\prod_{i=0}^r ((1+x)^{p^i})^{a_i} \\ &\equiv [x^k]\prod_{i=0}^r (1 + x^{p^i})^{a_i} \\ &\equiv \prod_{i=0}^r [x^{p^i b_i}](1 + x^{p^i})^{a_i}\\ &\equiv \prod_{i=0}^r \binom{a_i}{b_i}. \end{aligned}

• By the way, $$\binom{p^k}{n} \bmod{p}$$ and Lucas’s theorem is often seen in number theory problems in entrance exams of (Japanese) university. If you are a high-school student or younger, understanding these topics may help your studies, I guess?

#### Binomial coefficients $$\text{mod }2$$ and fractals

Although it is not directly relevant, I recently found this theme in AtCoder related to Lucas’s theorem, so I will briefly mention it.

We can apply Lucas’s theorem to $$p = 2$$ to see that binomial coefficients $$\text{mod }2$$ can be expressed by the following expression (where $$\mathrm{AND}$$ denotes bitwise logical product):

$\binom{n}{k} \bmod 2 = \begin{cases} 1 & n \text{ AND } k = k \\ 0 & \mathrm{otherwise} \end{cases}$

Another relative topic is that, if we paint odd-valued cells black in Pascal’s triangle (i.e. the cells in which the binomial coefficients $$\text{mod }2$$ equals $$1$$), a fractal structure called Sierpiński triangle appears. This can be proven by the property that the logical product of $$n$$ and $$k$$ relates to the parity.

Now let’s move on to the editorial.

### Solution 1: “skipping” every $$p^k$$ elements

Since $$\binom{p^k}{n} \bmod{p}$$ equals $$1$$ only if $$n=0,p^k$$, we can derive the following property:

$B_{i,j} \equiv B_{i+7^k,j} + B_{i+7^k,j+7^k} \pmod{7}$

Let $$R(i)$$ be the run-length compression of the $$i$$-th column. Then, we can compute $$R(i)$$ from $$R(i+7^k)$$ in an $$\mathrm{O}(|R(i+7^k)|)$$ time with the fact above. (Let us call this transition “skip.”)

Now let us “skip” every $$7^k$$ elements from the larger $$k$$ to smaller, while maintaining the value run-length-compressed. Formally, consider the algorithm expressed by the following pseudocode, where $$t$$ is the smallest integer such that $$N-K \lt 7^t$$:

// Calculate r = R(K)
r <- R(N)
n <- N
for i = t-1 to 0 do
while n - K >= 7^i do
r <- sequence jumping 7^i from r
n <- n - 7^i
end while
end for


Let’s analyze the complexity. The complexity of the algorithm above can be bounded by $$7$$ times the length of $$r$$ when the while statement in each iteration has ended, so it is sufficient to find the upper bound of the lengths of $$r$$.
Here, we can show the following two properties of the upper bound of the length of $$r$$ when the while statement for $$i = s$$ has ended:

• While the distance of skip remains the same, the length of run-length compressed sequence is multiplied by at most $$7$$, so we have an upper bound $$\mathrm{O}(M 7^{t-s})$$.
• When the while statement has ended, $$n \lt K + 7^s$$, and the length of $$r$$ is smaller than that. Therefore, we have an upper bound $$\mathrm{O}(K + 7^s)$$.

Since $$7^t = \mathrm{O}(N)$$, evaluating $$\min(\frac{MN}{x}, x + K)$$ is sufficient, which can be elementarily shown to be always no more than $$\sqrt{MN} + K$$. Therefore, the algorithm above works in $$\mathrm{O}((\sqrt{MN} + K) \log N)$$.

• More strictly, it is $$\Theta(\sqrt{MN} + K \log N)$$, so the problem can be solved even for the constraints about $$M \leq 5000$$.

Sample code, C++

### Solution 2: using Lucas’s theorem

Another way is to use Lucas’s theorem. We will explain it briefly. It is sufficient to enumerate

$B_{K,s} = \sum_{i=0}^{N-K} A_{s+i} \binom{N-K}{i}$

in the range $$1 \leq s \leq K$$. For convenience, hereinafter we use a sequence $$Q$$ satisfying $$Q_i = (a_{i}-a_{i+1}, \sum_{j\leq i}c_j)$$ (where $$a_{M+1}=0$$) instead of $$P$$. Then it holds that:

$B_{K,s} = \sum_{(a,c) \in Q} a \times \sum_{i=0}^{\min(N-K,c-s)}\binom{N-K}{i},$

in which

$\sum_{i=0}^n \binom{N-K}{i}$

can be computed with Lucas’s theorem and (digit DP or recursion) in an $$\mathrm{O}(\log N)$$ time, so we have boiled down to the form that can be computed in a total of $$\mathrm{O}(MK \log N)$$ time. (This is still an TLE (Time Limit exceeded) solution.)

We will speed it up even more. Trying to find $$B_{K,s}$$ while updating the differences of the expression above, without going into detail, it is boiled down to the problem of enumerating

$\binom{N-K}{L}, \binom{N-K}{L+1},\dots, \binom{N-K}{R}$

for some $$L$$ and $$R$$, which can be computed in an $$\mathrm{O}(\log N + R - L)$$ with Lucas’s theorem and recursions.
Eventually, we can use difference updates, so that the problem is solved in a total of $$\mathrm{O}((M + \log N) K + M \log N)$$ time.

Sample code, C++

posted:
last update: