I want to count the number of solutions to the problem $$x_1+x_2+\dots+x_n=k$$ subject to $0\le x_i\le c_i$ for each $i=1,2,\dots,n$.
I know that there are several answers on the site that deal with special cases or that give the theoretical solution via inclusion-exclusion etc. But I cannot apply them to my case (not clear enough or even too(ooo..) tedious). In my problem, I do not have "easy" numbers, that can be manipulated for a special approach: Think for e.g., $n=100, k=3000$ and $c_i=50$ for all $i=1,2,\dots,n$.
Is there a general analytical or numerical solution that would be easy to implement and compute by a program? Thank you.
First, some "theory" still. This number of solutions is equal to the coefficient of $x^k$ in $$\prod_{i = 1}^{n} (1 + x + \ldots + x^{c_i}) = (1 - x)^{-n} \prod_{i = 1}^{n} (1 - x^{c_i + 1}).$$ In the case of all equal $c_i = c$, it is then $[x^k]\left(\dfrac{1 - x^{c + 1}}{1 - x}\right)^n$.
If you hope to find a precise closed-form expression for this, you're probably out of luck even just for $c = 2$ and $k = n$ (when this is the central trinomial coefficient, see e.g. Theorem 8.8.1 here).
Thus we resort to iterative computations. A very simple ($\neq$ optimal) algorithm is obtained from $$F(c_1, \ldots, c_n; k) = \sum_{x = 0}^{\min\{k, c_n\}} F(c_1, \ldots, c_{n - 1}; k - x),$$ where the l.h.s. is the required number of solutions. Using an array $\mathtt{F[0..k]}$, initialized to the simple base case $n = 1$ (or even simpler $n = 0$) and updated in-place (from $\mathtt{F[k]}$ downwards; updating the sum above for transition $\mathtt{k} \to \mathtt{k - 1}$ is done with at most one addition and one subtraction) for increasing values of $n$, this algorithm will do $\mathcal{O}(nk)$ additions/subtractions on $\mathcal{O}(k)$ numbers (huge or not - depends on your setup).
For floating-point approximations, there is another approach, but let someone else explain it ;)