amr0's blog

Is There a Fast Way to Compute This Combinatoric Quantity?
By amr0, history, 5 years ago, In English

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!

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

what is the problem?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you have a link to the problem?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply