how to calculate ncr % M when the value of n has greater range(n <= 10^12). M = 10^9 + 7.
how to calculate ncr % M when the value of n has greater range(n <= 10^12). M = 10^9 + 7.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | maroonrk | 133 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
See Lucas' Theorem
For small M you can use Lucas's theorem.
For small N you can use Pascal's triangle.
For small R you can juse use slow algo in O(RlogM) by using factorial-formula.
Please do not reply presently for this doubt as it is from a running contest https://www.codechef.com/FEB16/problems/STROPR
Come on, if for example someone needs help with Dijkstra but there's some long challenge having a problem about Dijkstra's algorithm, do you think nobody should say a word about Dijkstra during the long contest? Moreover, where do you see that problem? I ran over all problems and the only one about permutations was this one — https://www.codechef.com/FEB16/problems/SEAPERMS. But I don't really see how it's related to the question asked in the blog and also N<=10^5 in the Codechef's problem.
Actually, it is related . I just solved it that way. But yes you are right. There's no harm helping him with what he has asked. Because even if he manages to find this, he still has a lot more to do.