Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

tactical-teto's blog

How many ways to pick AT MOST k elements from n elements?
By tactical-teto, history, 2 years 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 years ago, hide # |
← 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