f(n) = n*f(n-1) + f(n-2)
Can this be solved using matrix exponentiation ?
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Apr/25/2024 04:37:36 (j1).
Desktop version, switch to mobile version.
Supported by
Short answer: No. This is not a linear recurrence, since n isn't constant. Matrix multiplication can only be used for linear recurrences.
Long answer: Assuming F1 = 0 and F2 = 1, the first few terms of the sequence are: 0, 1, 3, 13, and 68. This is sequence A058307 in the OEIS. All formulas to calculate the nth term of this recurrence contain factorials of some form, and it seems impossible to make this recurrence linear. Matrix multiplication only works for linear recurrences, therefore the answer is no.