10175101159 edited 6 年，4 月前
题意即求$Fibonacci$数列${f_{n}}$的前$n$项和$S_{n}$。
在网上看到了关于$Fibonacci$数列一个有趣的性质：$S_{n}=f_{n+2}-1$。
于是本题转化为求一个$Fibonacci$数，但项数很大可以考虑矩阵快速幂。
现对公式尝试证明如下：
注意到$1+S_{n}=f_{2}+f_{1}+f_{2}+f_{3}+\cdots+f_{n}=f_{3}+f_{2}+f_{3}+\cdots+f_{n}=f_{4}+f_{3}+\cdots+f_{n}=\cdots=f_{n+1}+f_{n}=f_{n+2}$
因而$S_{n}=f_{n+2}-1$