M-candies extended problem

Revision en1, by SPyofgame, 2020-11-16 19:38:38

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

But what if the constraint 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 tried to find a better formula but I failed. I think this problem can be solved for general $$$a_i$$$ and $$$k$$$ in $$$O(n)$$$ or $$$O(n\ polylog\ n)$$$, can someone give me a hint ?

Tags combinatorics, math

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English SPyofgame 2020-11-18 03:18:16 0 Tiny change: 'rmula.\n\nCan so' -> 'rmula.\n\n\nCan so'
en5 English SPyofgame 2020-11-17 05:24:12 1309
en4 English SPyofgame 2020-11-16 20:10:33 70
en3 English SPyofgame 2020-11-16 19:53:07 87
en2 English SPyofgame 2020-11-16 19:41:28 153
en1 English SPyofgame 2020-11-16 19:38:38 13952 Initial revision (published)