斐波那契数列

一道让我做得相当高兴的题目。

原题链接 （这是付费比赛。）

题意简述

给定长度为 $n$ 的序列 $a$。定义函数 $f(S)=\sum\limits_{T\subseteq S} F^2(\sum_{s\in T} s)$，也即“对于 $S$ 的所有子集，求 $F(\text{子集所有元素之和})\text{的平方}$ 之和”。其中 $F(x)$ 为斐波那契数列的第 $x$ 项。有$F(0)=0, F(1)=1, F(x)=F(x-1)+F(x-2) (x > 1)$。

你需要支持以下操作，操作总数为 $m$：

1 x y：将 $a_x$ 修改为 $y$；

2 l r：输出 $\sum\limits_{i=l}^{r}\sum\limits_{j=i}^{r}f(\{a_i, a_{i+1}, \cdots, a_{j}\})$，对 $998244353$ 取模。

数据范围：对于 $\text{50\%}$ 的数据，有 $n,m\leq 100$；对于 $\text{70\%}$ 的数据，有 $n,m\leq 1000$；对于 $\text{100\%}$ 的数据，有 $n,m\leq 10^5, a_i \leq 10^5$。

（更多…）

广义斐波那契数列

定义：任何形如$f_i=f_{i-1}+f_{i-2}, f_1=x,f_2=y$的数列，称为广义斐波那契数列。

$F_1=F_2=1$的斐波那契数列的通项公式

$$F_n=\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right]$$

证明方法多样，可惜我都不会。知乎 – 斐波那契通项公式是怎样推导出来的？

下文中以$F_n$代指斐波那契数列的第$n$项，$f_n$代表广义斐波那契数列的第$n$项。

（更多…）