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......
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......
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 146 |
| 3 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
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.