Блог пользователя serasesi

Автор serasesi, история, 9 лет назад, По-английски

I want to find nCr(n choose r, if you will) modulo a prime. The trouble is that all the numbers i.e. n, r and prime are large and are of the order of 10^9.

One method I could come up with is computing each of the three factorials individually(using FFT and multipoint evaluation) but that seems too tedious. It may also timeout.

Is there anything else I can do ?

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
9 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +9 Проголосовать: не нравится

There is an ongoing competition with the same problem... :)

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

This problem is from an ongoing contest.

»
9 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +8 Проголосовать: не нравится

Can anyone explain the intended solution, now?
The editorial mentions caching factorials for 0, 106, 2 × 106, 3 × 106, ...!
How can this be achieved (once we have this it is easy to get factorials upto 2 × 109) efficiently?

  • »
    »
    9 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится

    Lets say you need to find x! where 2*109 > x.

    Now, we have stored 0! , 106 ! , 2*106 !, 3*106 ! .... and so on till 2000*106 ! .

    Now there will exist some integer 'z' such that z*106 <= x <= (z+1)*106.

    Since 'z' will always be <=2000, we would have already calculated z*106!
    Now note that the difference between (z+1)*106 and z*106 is 106.

    Therefore we would need to multiply the pre-calculated z*106! value by atmost 106 integers.