tacocat's blog

By tacocat, history, 5 months ago, In English

Given a fixed k (k<=1e6), make an array F of size n (n<=1e6) , with F[i] be the number of ways to pick AT MOST k elements from i elements.

Is there a way to create this array efficiently?

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
5 months ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

Fi is the number of ways to pick at most k elements from i elements total.

If you don't pick the first element, you have Fi1 ways to continue.

If you pick the first element, you need to choose at most k1 from the remaining i1. This is Fi1 minus the number of ways to pick exactly k from the remaining i1 elements, so Fi1(i1k).

In total Fi=2Fi1(i1k), you can compute the binomials quickly by precomputing factorials.

  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    can you explain the second choice (where you pick the first element) more ?

    Edit: Don't mind, I got it.