### XX86's blog

By XX86, history, 6 weeks ago, ,

How Can I solve this problem ! https://vjudge.net/problem/UVA-11904 Will be grateful if anyone can help. Thank You.

• +9

 » 6 weeks ago, # | ← Rev. 4 →   +9 You can solve this problem by changing the perspective to solve it from the back, imagine you have $k_1+k_2+\cdots+k_n$ time slots. Notice that, because every $job_i$ must be finished before finishing $job_{i+1}$, then the last time slot must be taken with the last job ($job_n$). So you must put one $job_n$ in the last time slot, and then, just fill the remaining time slots with $k_n-1$ of the last job. So we will have $C(k_1+k_2+\cdots+k_n-1,k_n-1)$ ways of filling this time slots. You can then just imagine throwing out away the time slots taken by $job_n$, then this problem goes out the same for the second last job, and then for the third last job and so on.You can solve this problem by using a simple $\text{prefix sum}$ ($pre[x]=\sum_{i=1}^{x}k_i$), and also $\text{precompute factorials}$ and $\text{inverse modulo factorials}$ to easily compute $\text{combinations}$. With all that in place, we will have the final answer, which is: $\left(\sum_{i=1}^{n}C(pre[i]-1, k_i-1)\right) \mod (10^9+7)$For reference, you can see my $\text{Accepted}$ code for this problem.
•  » » 6 weeks ago, # ^ |   0 thank you so much.