Hello Codeforcians!

I would like to know if there is an efficient method to calculate

where $$$k = N-(A+B+O+R)$$$ (of course all k's are greater than or equal zero), the output is modulo $$$1'000'000'007$$$, and $$$0\leq A,B,O,R, N\leq 400,000$$$. The time limit was 2 seconds, however any suggestions are more than welcome.

Thank you!

what is the problem?

A rat has N days and must eat at least A apples, B bananas,O oranges, and R rambutans in these N days. Find the number of different meal plans for these N days.

Can the rat eat more than one meal per day? Or it should eat at most one?

exactly one fruit a day

The answer is "Rat does not exist" Rat was eaten by the Cat.

Of course you can assume that $$$A,B,O,R\leq N$$$

you can write a for(O(n)) and calculate this sum_{k_A+k_B+k_O+k_R=k}{N\choose A+k_A,B+k_B,O+k_O,R+k_R} with O(1) with the modulo inverse (you can ask the complete and exact code from this handle alireza_kaviani he will tell you the complete code and implementation) good luck

Do you have a link to the problem?

https://codeforces.com/group/tglevT09th/contest/209483/problem/B

I saw your blog and solved the task code

The main idea is calculating two arrays $$$d_i$$$ — number of valid $$$i$$$ days plans just for bananas and apples and similar $$$c_i$$$ — for oranges and rambutan ( I do not know what is rambutan). Now answer is :

$$$\sum_{i=0}^{N}$$$ $$${N}\choose{i}$$$ $$$\cdot c_i \cdot d_{n-i}$$$

If you know how to calculate $$$d_i$$$, you know how to calulcate $$$c_i$$$ too.

$$$d_i$$$ = $$$2 \cdot d_{i-1}$$$ + $$${i-1}\choose{a}$$$ + $$${i-1}\choose{b}$$$.

First element is — if we had already valid plan for $$$i-1$$$ we can put anything on last place, other two elements are in case we do not have enough apples or bananas.

Thank you so much!