PUSSY_LICKING_LOLI_69's blog

How many ways to pick AT MOST k elements from n elements?
By PUSSY_LICKING_LOLI_69, history, 2 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

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

$$$F_i$$$ 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 $$$F_{i-1}$$$ ways to continue.

If you pick the first element, you need to choose at most $$$k-1$$$ from the remaining $$$i-1$$$. This is $$$F_{i-1}$$$ minus the number of ways to pick exactly $$$k$$$ from the remaining $$$i-1$$$ elements, so $$$F_{i-1} - \binom{i-1}{k}$$$.

In total $$$F_{i} = 2F_{i-1} - \binom{i-1}{k}$$$, you can compute the binomials quickly by precomputing factorials.

→ Reply
  • »
    »
    2 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.

    → Reply