### amr0's blog

By amr0, history, 8 months ago, ,

Hello Codeforcians!

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

$\sum_{k_A+k_B+k_O+k_R=k}{N\choose A+k_A,B+k_B,O+k_O,R+k_R}$

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!

• +6

 » 8 months ago, # |   +8 what is the problem?
•  » » 8 months ago, # ^ |   0 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.
•  » » » 8 months ago, # ^ |   0 Can the rat eat more than one meal per day? Or it should eat at most one?
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 exactly one fruit a day
•  » » » 8 months ago, # ^ |   0 The answer is "Rat does not exist" Rat was eaten by the Cat.
 » 8 months ago, # |   0 Of course you can assume that $A,B,O,R\leq N$
 » 8 months ago, # |   +8 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
 » 8 months ago, # |   0 Do you have a link to the problem?
•  » » 8 months ago, # ^ |   0
 » 8 months ago, # |   0 I saw your blog and solved the task codeThe 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.
•  » » 8 months ago, # ^ |   0 Thank you so much!