Hi, I am struck at this problem http://www.spoj.com/problems/SUMMUL/ . I think this can be solved using Matrix Exponentiation but I am unable to come up with the recurrence relation for this. Can someone please guide me towards the equations for this problem.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | jiangly | 3578 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | tourist | 3565 |
| 8 | maroonrk | 3531 |
| 9 | Radewoosh | 3521 |
| 10 | Um_nik | 3482 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 8 | SecondThread | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 30.04.2024 21:52:03 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
Let's also add a decomposition of n to the one term, the answer will be easier. Can you write any slow solution (DP or even bruteforce) to calculate it? It's really easy to guess the formula by values for small n.
Found the relation as you told: F(n) = 5*F(n-1)-8*F(n-2)+5*F(n-3)-F(n-4). But still can you tell me how to approach such type of problems? Thanks
Your coefficients looks correct. But in my first sentence i meant that there is an easier way: let's consider a function g(n) = f(n) + n. 1, 3, 8, 21, 55. Something familiar, isn't it? I don't know how I came up with this, though.
Generating functions are a rather universal way of solving such problems. I'm pretty sure that in this problem you can apply them, although I haven't tried.
We can write the recurrence relation as f(n + 1) = 3·f(n) - f(n - 1) + n and substituting g(n) gives g(n + 1) = 3·g(n) - g(n - 1) which is the bisection of Fibonacci sequence.
Once you get f(n+1) = 3*f(n) — f(n-1) + n you can solve it directly using matrix exponentiation. You don't need to reduce it again to a function g(n).
F(n+1) = 3*F(n) + (-1)*F(n-1) + 0*F(n-2) + 1*n
F(n) = 1*F(n) + 0*F(n-1) + 0*F(n-2) + 0*n
F(n-1) = 0*F(n) + 1*F(n-1) + 0*F(n-2) + 0*n
n = 0*F(n) + 0*F(n-1) + 0*F(n-2) + 1*n
You can express the 4 eq's in the form of a matrix.
Link:- http://zobayer.blogspot.in/2010/11/matrix-exponentiation.html.
That's the standard thing to do after finding the recurrence, but it's much more satisfying to represent it in terms of a known sequence.
f(N) = fibonacci(2*N) — N. I used this formula
We know that
.
Fn = 1(Fn - 1 + n - 1) + 2.(Fn - 2 + n - 2) + ...
Fn + 1 = (Fn + n) + 2.(Fn - 1 + n - 1) + ...
So, subtracting these terms we get
and
Subtracting these terms again we get Fn + 1 = 3Fn - Fn - 1 + n. We are lucky in this case as we can substitute Fn = gn - n to remove the polynomial term and solve it using matrix exponentiation. However, in the general it might not be so. But nevertheless, we can still find the solution in such cases. For example, take a look at this article. recurrences
It is easy to see that F(n)=F(n-1)*1+F(n-2)*2+F(n-3)*3+... but where do the terms (n-1)+(n-2)*2+... come from? @I_love_Equinox
well, you can see this as
F(n — 1) * 1 + 1 * (n — 1) + F(n — 2) * 2 + 2 * (n — 2) + ....
these 1 * n — 1 and 2 * n — 2 are added because now you can also split n into 1 and n-1, 2 and n — 2, 3 and n — 3, and so on ... which are new pairs.
it's been five years but still, maybe newcomers will understand it :)
You dont need to remove polynomial term, because if we store 1 and n in vector then n=(n-1)+1 and it is a linear transformation. Similarly n^2=(n-1)^2+2n-1 and so on.
As I am a novice will you please explain a bit more clearly?
Vector you need to maintain: v(n) = (F[n], F[n-1], n, 1). Just find a matrix A, so that A*v(n-1) = v(n). Then to find f(n) just compute (A^n)*v(0). If your polynomial terms were bigger your v would look something like: (f[n], f[n-1],1,n,n^2,n^3,...).
Thanks I didn't know that too,but my question was that how does one get to the basic recursive formula ?
I went through the comments by others which were helpful, but how can I derive the basic recursive formula or is it just intuition?