$\Large\mathscr{D}\mathcal{escription}$
一句话题意 $:$ 求
答案对 $998244353$ 取模。
$\Large\mathscr{S}\mathcal{olution}$
重点是要求 $\sum\limits_{i = 1}^n \text{Fib}_i \times i$,分母上的直接求逆元就行了。
刚开始以为是一道矩阵水题,就直接从后往前推,然后累加一下。
这样的话复杂度是 $\mathcal{O}(4^3Tlog_n)$。boom
所以还是得颓柿子$……$
首先,有一个结论 $:$ $\sum\limits_{i = 1}^n \text{Fib}_i$ $=$ $\text{Fib}_{n + 2} - 1$
证明 $:$
$\qquad$ 原式 $=$ $\text{Fib}_1 + \text{Fib}_2 + \text{Fib}_3 + …+\text{Fib}_n + 1 - 1$
$\qquad$ $\qquad$$=$ $\text{Fib}_1 + 2\text{Fib}_2 + \text{Fib}_3 + … + \text{Fib}_n - 1$
$\qquad$ $\qquad$$=$ $\text{Fib}_2 + 2\text{Fib}_3 + … + \text{Fib}_n - 1$
$\qquad$ $\qquad$$……$
$\qquad$ $\qquad$$=$ $\text{Fib}_{n + 2} - 1$
证毕。
然后就可以大力颓柿子了。
之后直接矩阵快速幂就好了。
$\Large\mathscr{C}\mathcal{ode}$
1 |
|