5
$\begingroup$

I want to compute the sum

$$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\binom{n}{6}+\dots+\binom{n}{k} \bmod 10^9+7$$

where $n$ and $k$ can be up to $10^{14}$ and $k\le n$.

I found several links on stack overflow to calculate sum of binomial coefficients but none of them works on large constraints like $10^{14}$. I tried doing it by changing series using the relation $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ and came up with a brute force solution which is of no use. Is there any way to do it efficiently?

This question is from the TCS codevita 2016 round 2 contest, which has ended.

$\endgroup$
  • $\begingroup$ Could you describe your brute force solution in a little more detail? $\endgroup$ – adrianN Aug 22 '16 at 15:07
  • $\begingroup$ @adrianN I used a loop to from 2 to k where on each iteration, I multiply (n-k)*(n-k-1) to Numerator and (k+1)*(k+2) to denominator of a variable whose initial value is n*(n-1)/2 and add this to sum and I initialized sum with (nC0+nC2). $\endgroup$ – srd091 Aug 22 '16 at 15:38
12
$\begingroup$

Hint: Use Lucas's theorem.

In general, any time a programming contest problem wants you to compute something mod $p$, check for opportunities to reduce everything mod $p$ before doing any further work.


Spoilers

Don't peek at any hint until you've spent a good amount of time thinking about the previous one!

A more in-depth hint if the previous wasn't enough:

Let $p=10^9 + 7$. Use Lucas's theorem to express $\binom{n}{i}$ in terms of functions of $n \bmod p$ and $i \bmod p$. Simplify the resulting sum by grouping terms.

If that's still not enough of a hint:

Consider the case where $k$ is a multiple of $p$. You should be able to come up with an efficient algorithm for that whose running time is something like $O(k/p)$.

Then for a final answer:

Generalize to the case where $k=ap+b$. You should be able to express this as a sum of the previous form, plus $b$ more terms. As a result you should be able to achieve a final running time of $O(p)$.

$\endgroup$
  • $\begingroup$ Thanks for answering. In the case where k=ap+b the solution will give TLE(time limit exceeded) error as p is of order 10^9. $\endgroup$ – srd091 Aug 24 '16 at 18:33
  • $\begingroup$ Is there any other way using Fast Fourier Transformation or something like that? $\endgroup$ – srd091 Aug 25 '16 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.