Can nCr % x (n choose r modulo any value)
computed by matrix exponentiation? if yes, how?
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.11.2024 20:29:14 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
i think you need fast method to calculate binomial coefficients for large n and k.
if n and k is less than 10^6, or mudule less than 10^6, you can precalc all factoials up to 10^6.
You can calculate Cnk in such a way for not prime modules too.
if n and k is less than 10^6, or mudule less than 10^6, you can precalc all factoials up to 10^6.
You can calculate Cnk in such a way for not prime modules too.
"You can calculate Cnk in such a way for not prime modules too." how can i calc it for not primes modules, since i am using euclids algorithm i cant get it right for not prime modules.
it's difficult to explain in a few words. look at the code
Your
ASS()function introduces undefined behavior, which can be anything, including the program continuing without any failure or subtly subverting the output data. Why not just useassert()from the standard library?Because it looks a way cooler that way.
this function introduces RE. assert() function will not work in release. can you offer me the right way?
Yes: the easiest way is to replace
++*(int*)0withabort().If N is very large (10^100 for example), and R is reasonably small (100 for instance), you can create (R+1)x(R+1) matrix A, which has ones on the main diagonal and on the diagonal above main, than compute v(A^N), where v is [1,0,0,0,...,0]. Last element of resulting vector will be the answer.
I believe this is what you were looking for
Can you/someone here please provide a problem link that needs this technique so that I can try my solution on that?
Thanks in advance :-)