In TCS codevita-2016 round 2 there was a question in which we need to calculate sum of even binomial coefficients like(\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\binom{n}{6}+…+\binom{n}{k})mod 10^{9}+7 where n and k can be upto 10^{14} and k<n.
3 Likes
ans= 2^(n-1)
that will be the answer when k is equal to n but I have clearly stated in question that k is less than n.
@srd091 Did anyone solve the problem during the contest or are there any solutions published by the author?
1 Like
@pranavarora the author did not publish any solution or editorial, and I don’t know the number of contestants who solved this problem.
My friend’s friend solved this problem and he said he solved it considering n<=10^5 instead of n<=10^9, pre-computed the factorial.
Here’s the code which is similar to what he said.
https://stackoverflow.com/questions/44962912/the-vita-sum-programming
Clearly,
\sum_{i=0}^{k/2} \binom{n}{2i} = \sum_{i=0}^{k} \binom{n-1}{i}.
In addition, if n = q_1 p + r_1 and k = q_2 p + r_2 (0 \le r_1, r_2 < p), then by Lucas theorem we have
\begin{aligned}
\sum_{i=0}^{k} \binom{n}{i} &= \sum_{j=0}^{q_2-1} \sum_{i=0}^{p-1} \binom{q_1 p + r_1}{jp+i}
+ \sum_{i=0}^{r_2} \binom{q_1 p +r_1}{q_2p+i} \\
&\equiv \sum_{j=0}^{q_2-1} \binom{q_1}{j} \sum_{i=0}^{p-1} \binom{r_1}{i} +
\binom{q_1}{q_2} \sum_{i=0}^{r_2} \binom{r_1}{i} \\
&\equiv 2^{r_1} \sum_{j=0}^{q_2-1} \binom{q_1}{j} +
\binom{q_1}{q_2} \sum_{i=0}^{r_2} \binom{r_1}{i} \pmod{p}. \\
\end{aligned}
So, we only need to compute the sum
\sum_{i=0}^{k} \binom{n}{i} \pmod{p},
where 0 \le k \le n < p.
In fact, this summation can be computed in O(\sqrt{p} \log p) time by using FFT/NTT.
Let v := \lfloor\sqrt{k}\rfloor, f_m(x) := \prod_{i=1}^{m}(x+i) and g_m(x) := \sum_{i=1}^{m} \left(\prod_{j=1}^{i-1}(n+1-j-x) \cdot \prod_{j=i}^{m} (x+j)\right). Then,
\sum_{i=0}^{k} \binom{n}{i} = \frac{1}{f_v(0)} \left(g_v(0) + \frac{f_v(n-v)}{f_v(v)} \cdot \left(g_v(v) + \frac{f_v(n-2v)}{f_v(2v)}\cdot\left(g_v(2v) + \cdots \right) \right) \right) + \sum_{i=v^2}^{k} \binom{n}{i}.
So, it suffices to evaluate f_v(iv), f_v(n-(i+1)v) and g_v(iv) for 0 \le i < v in O(\sqrt{k} \log{k}) time. (The last binomial sum can be computed in O(\sqrt{k} + \log{p}) time with those values.)
Firstly, the polynomials f_m(x) and g_m(x) satisfies the following recurrences
\begin{aligned}
f_{2m}(x) &= f_m(x) \cdot f_m(x+m)\\
g_{2m}(x) &= g_m(x) \cdot f_m(x+m) + g_m(x+m) \cdot f_m(n-m-x). \\
\end{aligned}
Secondly, by Lagrange interpolation and FFT, we can compute the values f(ai+c) (0 \le i \le \deg{f}) from f(ai+b) (0 \le i \le \deg{f}) in O(\textrm{M}(\deg{f})) time. (see https://specfun.inria.fr/bostan/publications/BoGaSc07.pdf.)
Therefore, we can compute the values f_{2m}(0), \ldots, f_{2m}(2mv) and g_{2m}(0), \cdots, g_{2m}(2mv) from f_{m}(0), \ldots, f_{m}(mv) and g_m(0), \ldots, g_m(mv) in O(m \log m) time. In addition, f_{2m+1}(*) and g_{2m+1}(*) can be computed from f_{2m}(*) and g_{2m}(*) in O(m + \log{p}) time. Thus, we can compute the binomial sum modulo prime in O(\sqrt{p} \log{p}) time.
[Updated]
It takes about 0.13 seconds on ideone to compute
\sum_{i=0}^{10^9} \binom{2 \cdot 10^9}{i} \equiv 1236371654 \pmod{2^{31} - 1}.
(C++ implementation: https://ideone.com/Q3e3Wo)
7 Likes