[BZOJ 2656][ZJOI2012]数列(递归+高精度)

题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=2656

分析:

很容易想到递归分治,但遇到奇数时候f[i]=f[i/2]+f[i/2+1]这样两个部分都分治去做,那么整个时间就退化到了线性。

不过容易发现:

f[23]=f[11]+f[12]

f[11]=f[5]+f[6]

f[12]=f[6]

所以要求f[11],f[12]只要求f[5],f[6]

f[5]=f[2]+f[3]

f[6]=f[3]

所以要求f[5],f[6]只要求f[2],f[3]

f[3]=f[1]+f[2]

f[2]=f[1]

所以只要求f[1],f[2]

这样能做到log2n级别的

上一篇:循序渐进学.Net Core Web Api开发系列【11】:依赖注入


下一篇:Spring 说明