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\).
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.
posted:
last update: