M-candies extended problem

Правка en3, от SPyofgame, 2020-11-16 19:53:07

Original Problem

M-candies-problem. In this version, we need to calculate the number of ways to share exact $$$K$$$ candies for all $$$N$$$ children that the $$$ith$$$-child doesnt have more than $$$a_i$$$ candies.

And the constraints are

  • $$$1 \leq N \leq 100$$$
  • $$$0 \leq K \leq 10^5$$$
  • $$$0 \leq a_i \leq K$$$
O(n * k^2) solution - Standard DP
O(n * k) solution - Prefixsum DP
O(n * k) solution - Online algo and space optimization


Extended Version

But what if the constraints were higher, I mean for such $$$M, a_i \leq 10^{18}$$$ limitation ?

O(1) solution for N = 1
O(1) solution for N = 2
O(1) solution for N = 3
O(1) solution for N = 4

Those fully-combinatorics codes above suck. I think this problem can be solved for general $$$a_i$$$ and $$$k$$$ in $$$O(n)$$$ or $$$O(n\ polylog\ n)$$$ with combinatorics or/and inclusion-exclusion, but I failed to find a general formula

Can someone give me a hint ?

Теги combinatorics, math

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский SPyofgame 2020-11-18 03:18:16 0 Tiny change: 'rmula.\n\nCan so' -> 'rmula.\n\n\nCan so'
en5 Английский SPyofgame 2020-11-17 05:24:12 1309
en4 Английский SPyofgame 2020-11-16 20:10:33 70
en3 Английский SPyofgame 2020-11-16 19:53:07 87
en2 Английский SPyofgame 2020-11-16 19:41:28 153
en1 Английский SPyofgame 2020-11-16 19:38:38 13952 Initial revision (published)