题解：P4834 萨塔尼亚的期末考试
Drink_Assam
·
·
题解
题意
给定 n，求 \frac{2}{n(n+1)}\sum_{i=1}^n F_i\cdot i 对 998244353 取模的结果。
其中，F_i 为斐波那契数列第 i 项。
前置知识：斐波那契前缀和
设 S_n=\sum_{i=1}^n F_i，有 S_n=F_{n+2}-2。
:::info[证明]{open}
不妨利用 F_n=F_{n-1}+F_{n-2} 乱推。
\begin{aligned}
{}&S_n=\sum_{i=1}^n F_i\\
=&F_1+F_2+\sum_{i=3}^n F_i\\
=&F_1+F_2+\sum_{i=3}^n (F_{i-1}+F_{i-2})\\
=&F_1+F_2+\sum_{i=1}^{n-2}F_i+\sum_{i=2}^{n-1}F_i\\
=&2F_1+F_2+F_{n-1}+2\sum_{i=2}^{n-2}F_i\\
=&F_2-F_{n-1}-2F_n+2\sum_{i=1}^{n}F_i\\
=&F_2-F_{n-1}-2F_n+2S_n
\end{aligned}
则 S_n=2F_n+F_{n-1}-F_2=F_n+F_{n+1}-1=F_{n+2}-1。
:::
回到本题，利用上述公式拆式子
\begin{aligned}
{}&\sum_{i=1}^n F_i\cdot i\\
=&\sum_{i=1}^n\sum_{j=1}^i F_i\\
=&\sum_{i=1}^n\sum_{j=i}^n F_j\\
=&\sum_{i=1}^n(S_n-S_{i-1})\\
=&\sum_{i=1}^n[(F_{n+2}-1)-(F_{i+1}-1)]\\
=&n\cdot F_{n+2}-\sum_{i=1}^n F_{i+1}\\
=&n\cdot F_{n+2}+F_1-\sum_{i=1}^{n+1} F_i\\
=&n\cdot F_{n+2}+1-(F_{n+3}-1)\\
=&n\cdot F_{n+2}-F_{n+3}+2
\end{aligned}
答案即为 \frac{2}{n(n+1)}\cdot(n\cdot F_{n+2}-F_{n+3}+2)。
其中 F_{n+2} 和 F_{n+3} 可以矩阵快速幂求，同 P1962。