Is there a stupid trick to calculate n-choose-k for a range of n with k always the same, which is faster than forming the full Pascal's triangle? With some fixed k, I need to calculate all n-choose-k modulo 10^9+7 for n up to 100,000 but there's no way I can calculate all the coefficients within 3 seconds.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | Petr | 145 |
| 9 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.05.2024 17:41:56 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
C(N, K) = N! / (K! * (N — K)!) => C(N + 1, K) = C(N, K) * (N + 1) / (N + 1 — K), that's obvious.
I think, you don't know how to perform the division, so please read about modular multiplicative inverse.
You can divide by x over a prime modulus M by multiplying by xM - 2. This lets you use factorial formula for n choose k.
Well, for that task you don't even need the fact that K is constant, if you precalculate all the factorials, you can answer the nCk query in logarithmic time.
Won't you answer the query in O(1) time then?
Nope, you will need to calculate modular inverse(O(logN)).
Actually, you can calculate modular inverse O(1) with O(n) pre-calculate.
Let rv[x] is the inverse of x under M, then rv[x] = rv[M % x] * (M — M / x) % M and of course rv[1] = 1.
That's awesome!! I'm eager to know why it works. Would you explain please?
let M = kx + r, r < x, then k = M / x, r = M % x and
both multiple rv[x] we will get
so,