How to solve the following recurrence relation for N ≤109
F(n)=F(n−1)+F(n−2)+F(n−1)∗F(n−2)
(Assuming that we are provided with the values of F(1) and F(2) )
(EDIT: The problem link is attached.)
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3845 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3630 |
| 4 | orzdevinwang | 3573 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | jqdai0815 | 3532 |
| 8 | ecnerwala | 3501 |
| 9 | gyh20 | 3447 |
| 10 | Rebelz | 3409 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | adamant | 163 |
| 3 | awoo | 161 |
| 4 | maroonrk | 152 |
| 4 | nor | 152 |
| 6 | -is-this-fft- | 151 |
| 7 | TheScrasse | 148 |
| 8 | atcoder_official | 146 |
| 9 | Petr | 145 |
| 10 | pajenegod | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.06.2024 10:40:46 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
$$$F(n) + 1 = (1 + F(n - 1)(1 + F(n - 2))$$$
Lets say $$$t_n = F_n + 1$$$, then $$$t_n = t_{n - 1} * t_{n - 2} $$$, expanding $$$t_n$$$ it can be realised that $$$t_n = t_0^{p_n} t_1^{q_n}$$$, where $$$p_n, q_n$$$ follows fibonacci recurrence.
I am getting the idea, just wanted to clarify that
Is pn always ≤ qn ?Yeah, you can prove it inductively. 2nd Term satisfies the condition and the third as well. Since from next term onwards, it's just the multiplication of the last two terms, pn≤qn for all of them.
How did you get the idea that pn and qn will follow fibbonacci recurrence
Try using induction, you will know.
Could you please help me debug my code?
I am getting a WA, although I tested at various random inputs with an accepted code.
Add 1 on both sides
1+F(n)= 1+F(n-1)+F(n-2)+F(n-1)*F(n-2)
1+F(n)=(1+F(n-1))*(1+F(n-2))
let g(n)=1+F(n)
-> g(n)=g(n-1)*g(n-2)
Now taking log on both sides
log(g(n))=log(g(n-1))+log(g(n-2))
let h(n)=log(g(n))
h(n)=h(n-1)+h(n-2)
Now the nth term of h can be found using matrix exponentation in O(log(n))
It's implied the value needs to be found under a modulo. In this method you need to find the discrete logarithm of the two starting values, which needs BSGS, and even worse, sometimes the discrete logarithm doesn't even exist.
If we have to find f(n)%MOD and MOD is prime then h(n) can be found under mod MOD-1 as h(n)=log2(g(n)) g(n)=2^h(n) and 2^(MOD-1)=1%MOD by Fermats Theorem so we can find h(n) under mod MOD-1 then g(n)=(2^(h(n)% MOD-1))%MOD
Therefore no need to take the logaritm its just for explanation.
can you explain more about when to take %MOD and %MOD-1 please.
// ^^ means exp
let u need to find (a^^p)%m, where m is prime.
and value of p cannot be stored, same as in this ques ==> fib powers cannot be stored.
using fermats theorem [ a^^(m-1) % m = 1 ]
(a^^p)%m = (a^^r)%m, where r = p % (m-1)
Got it. Thankyou manoj9april
Like so:
First, factor the recurrence to get
F(n)=(F(n-1)+1)(F(n-2)+1)-1.Then, set
G(n)=F(n)+1; we findG(n)=(F(n-1)+1)(F(n-2)+1)=G(n-1)G(n-2).Let
A=G(1)=F(1)+1andB=G(2)=F(2)+1. SinceG(n)will always be the product of some earlier terms, we can make a functionx(n)andy(n)so thatG(n)=A^(x(n))*B^(y(n)).We have the initial values
x(1)=1,x(2)=0,y(1)=0,y(2)=1and the recurrence relationsx(n)=x(n-1)+x(n-2),y(n)=y(n-1)+y(n-2). This is the same as Fibonacci but with different starting values.Use matrix exponentiation to find
x(n)andy(n), and then fast exponentiation to findA^(x(n))*B^(y(n)); the answer isA^(x(n))*B^(y(n))-1.Auto comment: topic has been updated by anupamshah_ (previous revision, new revision, compare).