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......
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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......
Name |
---|
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.