How to quickly find the value of each item in the following sequence.
$$$a_n=\lfloor (1+\sqrt{3})^n \rfloor$$$
Calculated in the sense of taking a mode.
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.11.2024 13:44:37 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by Limie (previous revision, new revision, compare).
Do you want to calculate all the values from 1 to n? or just for specific large n values?
It looks like you got this from the formula a_n = 2*(a_(n-1)+a_(n-2)).
If you want all values from 1 to n that'l take at least O(n) anyway so then use the recurrence
I only want to calculate one values.
then given the fact we know its equal to this recurence, we can use matrix exponentiation to calculate values in O(logn)
here's a post that explains about this a bit more.
but $$$\lfloor (1+\sqrt{3})^n \rfloor$$$ is not equal to the formula a_n = 2*(a_(n-1)+a_(n-2)).
True, i miscalculated, but here you can find the coefficients of a recurrence with the 4 previous elements. https://oeis.org/A080041
why a(n) = A080040(n) — (1+(-1)^n)/2？
No idea, but there are coefficiebts writenn for the recurrnece. Which is a_n = 2a_(n-1)+3a_(n-2)-2(a_(n-3)+a_(n-4))
But it's fast enough, since it's exponiental, it will only be calculted in log(n). Or is the problem of float relative error, if yes can you provide the equation that have this number as solution?
Sorry,I need to calculated in the sense of taking a mode.
Auto comment: topic has been updated by Limie (previous revision, new revision, compare).