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.
ans= 2^(n-1)
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,
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
So, we only need to compute the sum
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,
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
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
(C++ implementation: https://ideone.com/Q3e3Wo)
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?
@pranavarora the author did not publish any solution or editorial, and I don’t know the number of contestants who solved this problem.