UOJ Logo poorpool的博客

博客

#201. 第三产业数列 题解

2018-05-01 16:14:36 By poorpool

猜想答案为 $F_{2n}$。

证明: $$ \begin{align} F_{2n} &= \binom{1}{0}F_{2n-1}+\binom{1}{1}F_{2n-2} \\ &= \binom{1}{0}F_{2n-2}+\binom{1}{0}F_{2n-3}+\binom{1}{1}F_{2n-3}+\binom{1}{1}F_{2n-4} \\ &= \binom{2}{0}F_{2n-2}+\binom{2}{1}F_{2n-3}+\binom{2}{2}F_{2n-4} \end{align} $$ 以此类推。

矩阵快速幂加速即可。

评论

Capella
造题水平强啊

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。