suppose for any 'n' taken as input we want to output (2n)!/n!(n+1)! modulo 1000000007 then which is the fastest way to accomplish this task......
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
20:02:38
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
20:02:38
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 21:32:22 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
You can try to find a recurrence relation for your formula, then use matrix multiplication method to calculate Nth element of the sequence described by that recurrence relation.
Can you calculate this faster than
?
And how to calculate it for n / (log^2(n)) ?
I don't know. But if somebody can, I can calculate
faster than 
, and Burunduk1 once told me that 
is cool.
I'm not sure whether it is possible or not, but for example let's take the vector V = (n!, 0) and matrix M.
M =
V × M(n + 1) = V0 = (n!, (n + 1)!)
Let's take another matrix P.
P =
V0 × P = ((n + 1)!, 0)
So it means that (n!, 0) × M(n + 1) × P = ((n + 1)!, 0)
I mean to use something similar to multiply by matrix in logN time.
I think it's not possible, because the formula is non linear.
Actually
, which is not linear, but it can be represented in the following linear recurrence relation:
C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
I mean if we talk about Fibonacci numbers we have vector (f[n], f[n — 1]) and the next vector can be obtained multiplying it with constant matrix. In this case we can have (n!, n) but next vector is (n!*(n+1), n+1). The second element is OK, but to produce first one we need to multiply v[0] and (v[1] + 1). That is what i call non-linear formula.
But there is a way to calculate C(n, i) in O(N) time.
where r — row, c --column
source: wikipedia
n! can be calculated in O(n). congratulations.
Not n! I mean v_c = \choose{n}{c}
So, we will get C(n, 0), C(n, 1), C(n, 2), ..., C(n, n) in O(N) time. Without using pascal's triangle or smth else.
c[n][k] = n!/((n-k)!k!).
(2n)!/n!(n+1)! = 2^n / (n + 1). 2^n requires O(log n) time and 1 / (n + 1) % M is simply (n + 1)^(M — 2) % M (where M = 1000000007) because M is prime. So the total complexity is log M + log n which is fast enough I think
Ops.. I didn't mean that but you're right, my formula is wrong
Btw, (2n)!/n!(n+1)! is the n-th Catalan number. So the problem of it's calcilation must be well known. Am I wrong?
(2n)!/n!(n+1)!= c(2n,n)/(n+1)= c(2n,n)*(n+1)^(1000000005) Is it enough for you?:)
There isn't way to calculate C(2n,n) fast, is it?
I think there is the way to precalculate some numbers, and then answer the queries fast enough. There is only one test case? or many queries to find n-th Catalan number? we need to find all prime numbers between 1 and mod, and some additional information.