请问怎么快速求这个数列的第n项？不确定是否有得求，我yy出来的 - acm吧

level 7

A_Little_Black 楼主

如果能求，希望大佬传授给我吧， [真棒]

fn = f[n - 1］ + f［n - 2］+ add［pos］
add数组是-1 0 1 0 pos每次自增1，然后过了add数组长度后又回到开始那里。。 [黑线]

手机描述有点难，，希望你们能看懂。 [委屈]

2017年02月26日 11点02分 1

level 7

A_Little_Black 楼主

复杂度需要log

2017年02月26日 11点02分 2

level 7

A_Little_Black 楼主

如果看不懂请问我，，希望有套路解这种疑似规律又变来变去的题目 [泪]

2017年02月26日 11点02分 3

level 10

fourz238

pos和n的值有关吗？

2017年02月26日 12点02分 4

A_Little_Black

无关啊

2017年02月26日 12点02分

fourz238

怎么可能无关。pos是这式子的使用次数？

2017年02月26日 12点02分

A_Little_Black

@fourz238 就是控制加1，不变，减1，不变，这样重复而已

2017年02月26日 13点02分

level 7

A_Little_Black 楼主

比如这个数列是
2
4
6
9
15
25
40
64
104
169
273
441
714
1156
1870

2017年02月26日 12点02分 5

level 4

zY-Kfhh

你去wolfram alpha求一下通向公式这个应该分成一个fib数列配一个周期数列如果通向公式能分得开那就分开求快速矩阵幂最后把周期数列的和加上

2017年02月26日 12点02分 6

A_Little_Black

啊？？？

2017年02月26日 12点02分

A_Little_Black

那里没得求通项呀

2017年02月27日 00点02分

level 7

A_Little_Black 楼主

原来这题是有解的

有oj。。不过做法不是我这么笨 [惊哭]

2017年02月27日 00点02分 7

level 7

A_Little_Black 楼主

有大神吗

2017年02月28日 03点02分 8

level 8

终然独不见º💧

这不就是斐波那契数组吗……加了个加1减1……

2017年03月05日 16点03分 9

A_Little_Black

嗯，怎么求？

2017年03月06日 00点03分

终然独不见º💧

@A_Little_Black 建议不要闭门造车，很多算法书上都有相关问题，看下大白书 [滑稽]

2017年03月06日 05点03分

A_Little_Black

@终然独不见º💧

说下怎么求啊，

2017年03月06日 07点03分

A_Little_Black

@终然独不见º💧 我的错 [小红脸]

大佬教训得是

2017年03月06日 15点03分

level 7

A_Little_Black 楼主

http://acm.hdu.edu.cn/showproblem.php?pid=2604

2017年03月07日 00点03分 10

level 7

A_Little_Black 楼主

上面那个是题目，这题我训练的时候卡了我O(9n)的dp，所以很不爽，找到了那个数字的规律后，却不会构造矩阵，白白丢了一题。正解是矩阵快速幂，可以百度下，也可以ac自动机的，。先说说怎么破这条方程吧。（我旧队友告诉我的）

2017年03月07日 00点03分 11

level 7

A_Little_Black 楼主

首先可以找到的是每个数字都是两个fib数列的和，这个没啥用，留作纪念而已

2017年03月07日 01点03分 12

level 7

A_Little_Black 楼主

注意到他是四个一循环，就是-1、0、+1、0、......不断重复，那么，我们把
F[n] + F[n - 1] + F[n - 2] + F[n - 3]合并，那么就会使得加权变成0
最后得到的公式是
F[n] = F[n - 2] + F[n - 3] + 2 * F[n - 4] + F[n - 5]
这个可以矩阵快速幂

2017年03月07日 01点03分 13

A_Little_Black

操几年后居然不会做

2022年06月05日 06点06分