Share exact K candies to all children with a limitation of a child can get

Revision en6, by SPyofgame, 2020-11-18 03:18:16

### 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 and hard to gets a simplified formula. Though 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 such formula.

Can someone give me a hint ?

#### History

Revisions

Rev. Lang. By When Δ Comment
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)